[Data Structure] 자료구조 - 연결 리스트(Linked List) - 이중 연결 리스트(Double Linked List)

3. 이중 연결 리스트

이번에는 이중 연결 리스트에 대해 포스팅을 진행해 보도록 하겠습니다!!!

개념: 노드에 두 개의 링크 필드와 한 개의 데이터 필드로 구성된 연결리스트 입니다!!

그림으로 삽입, 삭제 연산을 먼저 짚고 넘어가죠!!!

다시 등장한 우리의 진짜 사나이들!!!

이제는 서병장, 호주 물개, 선착수로를 못 본다는게 슬프네요 ㅠㅠ

자 이렇게 서로 서로 참조를 하고 있는 구조가 이중 연결 리스트 입니다.

삽입 연산

여기서 수로형님이 샘과 헨리의 중간에 삽입이 된다고 보죠!!

이렇게 들어갔습니다!!!

그럼 링크에 대해 수정이 좀 가해지겠죠???

먼저 

김수로의 왼쪽 참조를 샘으로 설정!!!

그러고나서 김수로의 오른쪽 참조를 헨리로 설정!!!

 

그리고 샘의 오른쪽 참조를 김수로로 설정하고

헨리의 왼쪽 참조를 김수로로 설정합니다!!!

이렇게 해서 삽입이 끝났네요~~

삭제 연산

자 이번에는 호주 물개가 빠집니다~

보시죠~

 

먼저 이렇게 경석의 오른쪽 참조가 수로를 참조하게되고

수로의 왼쪽 참조가 경석을 참조하게 합니다!!

그렇게 하고 샘을 빼주면 되요!!!

 

 

이렇게 하면 삭제 연산이 끝이 납니다!!!!

자 바로 소스 코드를 통해 확인해 보겠습니다!!!

DblNode.java

 

 

 

 
package doubleLink;
 
public class DblNode {
    private DblNode lLink;
    private String data;
    private DblNode rLink;
 
    public DblNode() {
        this.lLink = null;
        this.data = null;
        this.rLink = null;
    }
 
    public DblNode(String data) {
        this.lLink = null;
        this.data = data;
        this.rLink = null;
    }
 
    public DblNode getlLink() {
        return lLink;
    }
 
    public void setlLink(DblNode lLink) {
        this.lLink = lLink;
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public DblNode getrLink() {
        return rLink;
    }
 
    public void setrLink(DblNode rLink) {
        this.rLink = rLink;
    }
 
}
 

DoubleLinkedList.java

 

 
package doubleLink;
 
public class DoubleLinkedList {
    private DblNode head;
 
    public DoubleLinkedList() {
        head = null;
    }
 
    public void insertFirstNode(String data) {
        DblNode newNode = new DblNode(data);
        DblNode tmp;
        if (head == null) {
            this.head = newNode;
        } else {
            tmp = head;
            tmp.setlLink(newNode);
            newNode.setrLink(tmp);
            head = newNode;
        }
    }
 
    public void insertMiddleNode(DblNode pre, String data) {
        DblNode newNode = new DblNode(data);
        DblNode post = pre.getrLink();
        if (post == null) { // 삽입할 노드가 마지막일 경우
            pre.setrLink(newNode);
            newNode.setlLink(pre);
        } else { // 삽입할 노드 뒤에 노드가 있는 경우
            newNode.setlLink(post.getlLink()); // 삽입할 노드의 왼쪽링크를 post의 왼쪽링크
            newNode.setrLink(pre.getrLink()); // 삽입할 노드의 오른쪽링크를 pre의 오른쪽 링크
            pre.setrLink(newNode); // 삽입할 노드의 이전 노드의 오른쪽 링크를 삽입할 노드로
            post.setlLink(newNode); // 삽입할 노드의 이후 노드의 왼쪽 링크를 삽입할 노드로
        }
    }
 
    public void insertLastNode(String data) {
        DblNode newNode = new DblNode(data);
        DblNode tmp = this.head;
 
        if (tmp == null) {
            this.head = newNode;
        } else {
            while (tmp.getrLink() != null) {
                tmp = tmp.getrLink();
            }
            tmp.setrLink(newNode);
        }
    }
 
    public void deleteNode(DblNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
 
            DblNode old = pre.getrLink();
            if (old == null) {
                return;
            }
 
            DblNode post = old.getrLink();
 
            // 뒤에 노드있으면 서로 연결
            if (post != null) {
                pre.setrLink(post);
                post.setlLink(pre);
            } else { // 뒤에 노드가 없으면 링크 제거
                pre.setrLink(null);
            }
        }
    }
 
    public void deleteLastNode() {
        DblNode pre = this.head;
        DblNode tmp;
        if (head == null) {
            System.out.println("리스트가 비어있습니다!!");
            return;
        } else {
            tmp = head.getrLink();
 
            while (tmp.getrLink() != null) {
                pre = tmp;
                tmp = tmp.getrLink();
            }
 
            pre.setrLink(null);
        }
    }
 
    public DblNode searchNode(String data) {
        DblNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData()) {
                return tmp;
            } else {
                tmp = tmp.getrLink();
            }
        }
 
        return tmp;
    }
 
    public void printList() {
        DblNode tmp = this.head;
 
        System.out.print("DL = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getrLink();
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
 
}
 

DoubleMain.java

 

 
package doubleLink;
 
public class DoubleMain {
    public static void main(String[] args) {
        DoubleLinkedList DL = new DoubleLinkedList();
 
        System.out.println("(1) 삽입 연산 수행");
        DL.insertFirstNode("화");
        DL.insertFirstNode("월");
        DL.insertLastNode("목");
        DblNode pre = DL.searchNode("화");
        DL.insertMiddleNode(pre, "수");
        DL.printList();
 
        System.out.println("(2) 마지막 노드 삭제 연산 수행");
        DL.deleteLastNode();
        DL.printList();
 
        System.out.println("(3) 중간 노드 삭제 연산 수행");
        pre = DL.searchNode("월");
        DL.deleteNode(pre);
        DL.printList();
    }
}
 

결과는 아래와 같습니다!!