데이터 구조와 알고리즘의 체인 테이블 (5) 쌍체인 테이블 실현

인용문
앞의 몇 편의 글은 단일 체인 시계의 조작을 상세하게 배웠고 이 기초를 닦았기 때문에 이중 체인 시계의 실현은 쉽게 이루어졌다.그것의 기본적인 실현은 단사슬표와 기본적으로 같기 때문에 본 편은 그것의 실현을 간단하게 설명하고 세부 원리는 더 이상 상세하게 설명하지 않는다.
쌍사슬표 실현
1. 인터페이스와 실현: 단일 체인 테이블의 실현 인터페이스와 일치

public interface IList {
    int size();

    boolean isEmpty();

    void clear();

    boolean contains(T item);

    boolean add(T item);

    T get(int index);

    T set(int index, T item);

    void add(int index, T item);

    T remove(int index);
}

삭제와 증가된 조작 위치를 통일적으로 하기 위해 데이터가 없는 두결점과 꼬리 요소를 가리키는 꼬리 지침을 도입한다. 이렇게 증가와 삭제 조작은 두 가지 상황으로 나뉘는데 그것이 바로 꼬리 조작과 중간 조작이다.

/**
 * Created by chenming on 2018/5/26
 */
public class DLinkedList implements IList {

    private DNode head; //        
    private DNode tail; //       


    public DLinkedList() {
        //      
        this.head = this.tail = new DNode<>();
    }
    ......
}

2. 노드: 단일 체인 테이블에 비해 선행 포인터가 더 많다.

package List.dlinkedlist;

/**
 * Created by chenming on 2018/5/26
 */
public class DNode {
    public T data;
    public DNode prev, next;//         

    public DNode(T data, DNode prev, DNode next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }

    public DNode(T data) {
        this(data, null, null);
    }

    public DNode() {
        this(null, null, null);
    }
}

3. 원소를 추가하는 것은 단일 체인 테이블과 유사하며 꼬리 추가와 중간 추가로 나뉜다.

    /**
     *         
     *
     * @param index
     * @param item
     */
    @Override
    public void add(int index, T item) {
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        if (item == null) {
            return;
        }

        DNode preNode = this.head;
        int j = 0;
        //               
        while (preNode.next != null && j < index) {
            j++;
            preNode = preNode.next;
        }
        //         ,         front,      front.next
        DNode newNode = new DNode<>(item, preNode, preNode.next);
        //     preNode                
        if (preNode.next != null) {
            preNode.next.prev = newNode;
        }

        //preNode          
        preNode.next = newNode;

        if (preNode == tail) {//      ，      
            tail = newNode;
        }
    }

    /**
     *       
     *
     * @param item
     * @return
     */
    @Override
    public boolean add(T item) {
        if (item == null) {
            return false;
        }

        //         ,         tail,      tail.next
        DNode newNode = new DNode<>(item, tail, tail.next);
        //tail          
        tail.next = newNode;
        //  tail
        tail = newNode;
        return true;
    }

4. 요소 삭제: 끝 삭제와 중간 삭제로 나뉜다.

    /**
     *     
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        int size = size();

        if (index < 0 || index >= size || isEmpty()) {
            return null;
        }

        DNode p = this.head.next;
        int j = 0;
        //        ,index = 0  head.next，     j <= index
        while (p != null && j < index) {
            p = p.next;
            j++;
        }
        if (j >= size()) {//    
            throw new IndexOutOfBoundsException();
        }
        //        
        if (p.next != null) {
            p.next.prev = p.prev;
        }
        p.prev.next = p.next;
        //         tail p     
        if (p == tail) {
            tail = p.prev;
        }
        return p.data;
    }

    /**
     *     item  
     * @param item
     * @return
     */
    public boolean removeAll(T item) {
        boolean result = false;
        if (item == null || isEmpty()) {
            return result;
        }
        DNode p = this.head.next;
        while (p != null) {
            if (item.equals(p.data)) {//    
                if (p == tail) {//p     .       ,  p
                    tail = p.prev;
                    tail.next = null;
                    p.prev = null;
                } else {//      
                    p.prev.next = p.next;
                    p.next.prev = p.prev;

                }
                result = true;
            }

            p = p.next;//    
        }
        return result;
    }

5. 요소를 읽고 설정합니다.

    @Override
    public T get(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        int j = 0;
        DNode node = this.head.next;
        while (node != null && j < index) {
            node = node.next;
            j++;
        }
        if (j >= size()) {//    
            throw new IndexOutOfBoundsException();
        }
        if (node != null) {
            return node.data;
        }
        return null;
    }
    /**
     *     
     *
     * @param index
     * @param item
     * @return
     */
    @Override
    public T set(int index, T item) {

        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        if (index >= size()) {//    
            throw new IndexOutOfBoundsException();
        }

        T old = null;
        int j = 0;
        DNode node = this.head.next;
        while (node != null && j < index) {
            node = node.next;
            j++;
        }

        if (node != null) {
            old = node.data;
            node.data = item;
            return old;
        }
        return null;
    }

6. 기타 방법:

/**
     *     
     *
     * @return
     */
    @Override
    public int size() {
        int size = 0;
        DNode node = head.next;// head.next  
        while (node != null) {
            node = node.next;
            size++;
        }
        return size;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public void clear() {
        head = tail = new DNode<>();
    }

    @Override
    public boolean contains(T item) {
        if (item == null) {
            return false;
        }
        DNode p = head.next;
        while (p != null) {
            if (item.equals(p.data)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

JDK의 링크드 리스트는 쌍체인표를 바탕으로 이루어진 것으로 이를 바탕으로 최적화를 했고 구체적인 실현 방법은 뒤에 있는 링크드 리스트 원본 분석에서 설명할 것이다.전체 코드 주소: 데이터 구조와 알고리즘 학습 JAVA 설명GayHub 주소