Lecture/자료구조/2011/4.6 이중 연결 리스트

DoubleListNode.java

/**
 * 이중 연결 리스트에서 노드를 표현하기 위한 클래스이다.
 * 이 노드를 생성하면 기본적으로 모든 변수는 null이 된다.
 * Java에서는 변수의 값을 null로 설정하지 않아도 기본적으로 null이 된다.
 */
public class DoubleListNode {
    Object data = null;
 
    DoubleListNode rlink = null;
    DoubleListNode llink = null;
}

DoubleLinkedList.java

public class DoubleLinkedList {
    DoubleListNode head = null;
    DoubleListNode tail = null;
    int length = 0;
 
    /**
     * 노드 p를 삭제한다.
     * @param p 삭제하고자 하는 노드
     */
    public void delete(DoubleListNode p) {
        if (p == null)
            return;
        if (p.llink != null)
            p.llink.rlink = p.rlink;
        if (p.rlink != null)
            p.rlink.llink = p.llink;
        length--;
    }
 
    /**
     * 노드 p 뒤에 노드 q를 삽입한다.
     * @param p 이 노드는 반드시 null이 아니어야 한다.
     * @param q 삽입하고자 하는 노드
     */
    public void insert(DoubleListNode p, DoubleLinkedList q) {
        q.llink = p;
        q.rlink = p.rlink;
        if (p.rlink != null)
            p.rlink.llink = q;
        p.rlink = q;
        length++;
    }
}