ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Data Structure] 자료구조 - 연결 리스트(Linked List) - 이중 연결 리스트(Double Linked List)
    CSE/Data Structure 2015. 6. 12. 16:10

    3. 이중 연결 리스트





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



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



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




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




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








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





    삽입 연산






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








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


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






    먼저 


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







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






     



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

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






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







    삭제 연산




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



    보시죠~






     



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

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



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




     



     



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




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


    DblNode.java




     


     

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
     
    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;
        }
     
    }
     
    cs



    DoubleLinkedList.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
     
    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(")");
        }
     
    }
     
    cs




    DoubleMain.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     
    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();
        }
    }
     
    cs




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



     








    댓글

Designed by Tistory.