02-4 이중 연결 리스트

※ 이중 연결 리스트

단순 연결 리스트는 선행 노드에 접근하기가 어렵다. 그래서 이를 개선하기 위해 원형 연결 리스트를 구성했다.

하지만 원형 연결 리스트에서도 현재 노드의 선행 노드에 접근하기 위해서는 전체 리스트를 한바퀴 순회해야 하는 문제가 생긴다.

이러한 문제점들을 보완하기 위해 이중 연결 리스트(Doubly Linked List)가 있다.

앞에서 배운 연결 리스트들은 link가 하나였고 다음 노드값들을 저장해 두었다.

하지만 이중연결 리스트는 노드에 link부분을 앞뒤로 두어 선행노드와 후행노드를 각각 연결해둔다. 그래서 선행노드의 접근이 다른 연결 리스트에 비해 쉽다.

※ 구현(아래 이중 연결 리스트로 구현한다)

메인

public class Main {

      public static void main(String[] args) {

            DoublyLinkedList list = new DoublyLinkedList();

            //insert Frist Node

            Node wen = new Node("금");

            list.firstInsertNode(wen);

            Node thu = new Node("화");

            list.firstInsertNode(thu);

            Node mon = new Node("월");

            list.firstInsertNode(mon);

            list.printList();

            //insert moddle node

            Node pre1 = list.searchNode("토");

            list.insertMiddleList(pre1,"수");

            Node pre2 = list.searchNode("화");

            list.insertMiddleList(pre2,"수");

            Node pre3 = list.searchNode("수");

            list.insertMiddleList(pre3,"목");

            Node pre4 = list.searchNode("금");

            list.insertMiddleList(pre4,"토");

            Node pre5 = list.searchNode("토");

            list.insertMiddleList(pre5,"일");

            list.printList();

            System.out.println();

            Node del1 = list.searchNode("월");

            list.deleteNode(del1);

            Node del2 = list.searchNode("일");

            list.deleteNode(del2);

            Node del3 = list.searchNode("목");

            list.deleteNode(del3);

            list.printList();

            System.out.println();

            list.reverseNode();

            list.printList();

      }

}

노드

public class Node {

      private String data;

      public Node l_link;

      public Node r_link;

      public Node(String data) {

            this.data = data;

            this.l_link = null;

            this.r_link =null;

      }

      public Node() {

            this.data = null;

            this.l_link = null;

            this.r_link =null;

      }

      public String getData(){

            return this.data;

      }

}

이중 연결 리스트

public class DoublyLinkedList {

      public Node head;

      public Node tail;

      public DoublyLinkedList(){

            this.head = null;

            this.tail = null;

      }

      //search node

      public Node searchNode(String data){

            Node searchNode = new Node();

            searchNode = head;

            while(searchNode != tail){

                  if(searchNode.getData().equals(data)){

                        return searchNode;

                  }else{

                        searchNode = searchNode.r_link;

                  }

            }

            //last node

            if(searchNode.getData().equals(data)){

                  return searchNode;

            }else{

                  System.out.println("찾는 데이터가 없습니다.");

                  return null;

            }

      }

      //insert

      public void firstInsertNode(Node insertNode){

            //linked list length zero

            if(head == null){

                  head = insertNode;

                  tail = insertNode;

                  insertNode.l_link = tail;

                  insertNode.r_link = head;

            }

            else {

                  //linked list length not zero

                  Node temp = new Node();

                  temp = head;

                  insertNode.l_link = tail;

                  insertNode.r_link = head;

                  tail.r_link = insertNode;

                  head.l_link = insertNode;

                  head = insertNode;

            }

      }

      public void insertMiddleList(Node pre, String data){

            if(pre == null){

                  System.out.println("");

                  return;

            }

            Node temp = new Node();

            Node newNode = new Node(data);

            temp =head;

            //middle node insert

            while(temp != tail){

                  if(temp == pre){

                        newNode.r_link = temp.r_link;

                        newNode.l_link = temp;

                        temp.r_link.l_link = newNode;

                        temp.r_link = newNode;

                        return;

                  }else{

                        temp = temp.r_link;

                  }

            }

            //last node insert

            if(temp == tail){

                  temp.r_link = newNode;

                  newNode.r_link = head;

                  newNode.l_link = temp;

                  tail = newNode;

            }

      }

      //delete

      public void deleteNode(Node delNode){

            Node temp = head;

            if(delNode == head){

                  head = temp.r_link;

                  tail.r_link =temp.r_link;

                  head.l_link = tail;

            }else if(delNode == tail){

                  tail.l_link.r_link = head;

                  tail = tail.l_link;

                  head.l_link = tail;

            }else{

                  while(temp != tail){

                        if(temp == delNode){

                              temp.l_link.r_link = temp.r_link;

                              temp.r_link.l_link = temp.l_link;

                              return;

                        }else{

                              temp = temp.r_link;

                        }

                  }

            }

      }

      //print list

      public void printList(){

            Node temp = new Node();

            temp = head;

            int idx = 1;

            while(temp != tail){

                  System.out.println("index : " + idx + ", data : " + temp.getData());

                  temp =temp.r_link;

                  idx ++;

            }

            System.out.println("index : " + idx + ", data : " + temp.getData());

      }

      //reverse list

      public void reverseNode(){

            Node pre = null;

            Node current = null;

            Node next = head;

            next = head;

            while(current != tail){

                  pre = current;

                  current = next;

                  next= next.r_link;

                  current.r_link = pre;

                  current.l_link = next;

            }

            if(current == tail){

                  head = current;

                  tail = current.l_link;

            }

      }

}