[자료구조][이중 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 6

 

 

 

 

[이전 글]

2024.01.26 - [코딩테스트] - [자료구조][단일 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 5

[자료구조][단일 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 5

 

---

 

• Linked List 란?
  • 데이터의 집합을 나타내는 지료구조로, 각 데이터 요소를 노드(Node)라고 칭한다.
  • 각 노드는 데이터 필드와 다음 노드를 가리키는 링크(포인터)로 구성
  • 배열과 달리 메모리에 연속적으로 배치되지 않으며, 동적으로 크기가 조절된다.

 

• 주요 특징과 용어
  • 노드(Node) : 데이터와 다음 노드를 가리키는 링크로 구성된 기본 단위
  • 헤드(Head) : 링크드 리스트의 첫 번째 노드
  • 테일(Tail) : 링크드 리스트의 마지막 노드 (일부 구현에서는 테일이 없는 경우도 있음)
  • 링크(Link) : 각 노드가 다음 노드를 가리키는 참조

 

• 링크드 리스트의 종류 
  • 단일 연결 리스트 (Singly Linked List) : 각 노드가 다음 노드를 가리키는 구조
    • 장점 : 구현이 간단하고 일반 배열의 단점(데이터 추가, 삭제)을 보완
    • 단점 : 첫 노드 부터 다음 노드 순으로 순차적으로 노드를 찾아야 하는 구조여서 마지막 노드를 찾을 경우 느림
  • 이중 연결 리스트 (Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 구조
    • 장점 : 단일 연결 리스트의 단점을 보완하여 양방향으로 노드를 연결하여 리스트 앞, 뒤로 탐색이 모두 가능
    • 단점 : 메모리 공간을 단일 연결 리스트 보다 더 사용, 구현 복잡도 증가, 추가적인 연산 시간 복잡도
  • 순환 연결 리스트 (Circular Linked List) : 마지막 노드가 첫 번째 노드를 가리키는 구조

 

출처: 위키백과 더블 링크드 리스트

 

 

 

• 이중 연결 리스트 예제
  • 철수는 쉬는 시간이 시작 하자 마자 매점에 갔다. 첫번째로 도착한 철수는 1번으로 간식을 산다. 
  • 그 뒤로 수미가 왔고 순서대로 임정, 정희, 지웅이 줄을 섰다. 
  • 영이는 뒤늦게 왔는데 수미 앞으로 세치기를 하고, 정희는 다른 일이 생겨 매점에서 나간다. 

 

package linkedlist;

public class DoubleLinkedListTest {
    public static class Node<T> {
        T data;

        Node<T> prev = null;
        Node<T> next = null;

        public Node(T data) {
            this.data = data;
        }
    }

    public static class DoubleLinkedList<T> {
        public Node<T> head = null; // 첫번째 노드
        public Node<T> tail = null; // 마지막 노드

        public void addNode(T data) {
            if (head == null) {
                head = new Node<T>(data);
                tail = head;
            } else {
                Node<T> node = this.head;
                while (node.next != null) {
                    node = node.next;
                }

                node.next = new Node<T>(data);
                node.next.prev = node;
                this.tail = node.next;
            }
        }

        public void printAll() {
            if (head != null) {
                Node<T> node = this.head;
                printNode(node);
                while (node.next != null) {
                    node = node.next;
                    printNode(node);
                }
                System.out.println();
            }
        }

        private void printNode(Node<T> node) {
            if (node.prev != null)
                System.out.print("<prev:" + node.prev.data + ">");
            else
                System.out.print("<prev:" + null + ">");
            System.out.print("[" + node.data + "]");
            if (node.next != null)
                System.out.println("<next:" + node.next.data + ">");
            else
                System.out.println("<next:" + null + ">");
        }


        /**
         * 특정 노드 앞에 신규 노드 추가
         *
         * @param existedData : 기존 노드
         * @param addData     : 신규 노드
         * @return
         */
        public boolean insertToFront(T existedData, T addData) {
            if (this.head == null) {
                this.head = new Node<T>(addData);
                this.tail = this.head;
            } else if (this.head.data == existedData) {
                Node<T> newHead = new Node<T>(addData);
                newHead.next = this.head;
                this.head = newHead;
                return true;
            } else {
                Node<T> node = this.head;
                while (node != null) {
                    if (node.data == existedData) {
                        Node<T> nodePrev = node.prev;
                        nodePrev.next = new Node<T>(addData);
                        nodePrev.next.next = node;
                        nodePrev.next.prev = nodePrev;
                        node.prev = nodePrev.next;
                        return true;
                    } else {
                        node = node.next;
                    }
                }
            }
            return false;
        }

        public boolean removeNode(T data) {
            if (head != null) {
                Node<T> node = head;
                if (node.data == data) {
                    this.head = this.head.next;
                    return true;
                } else {
                    while (node.next != null) {
                        if (node.next.data == data) {
                            node.next = node.next.next;
                            node.next.prev = node;
                            return true;
                        }
                        node = node.next;
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        DoubleLinkedList<String> linkedList = new DoubleLinkedList<>();
        linkedList.addNode("철수");
        linkedList.addNode("수미");
        linkedList.addNode("임정");
        linkedList.addNode("정희");
        linkedList.addNode("지웅");
        linkedList.printAll();
        System.out.println("> 수미 전에 영이 추가");
        linkedList.insertToFront("수미", "영이");
        linkedList.printAll();
        System.out.println("> 정희 이탈");
        linkedList.removeNode("정희");
        linkedList.printAll();
    }
}

/**
 * [결과 값]
 
 <prev:null>[철수]<next:수미>
 <prev:철수>[수미]<next:임정>
 <prev:수미>[임정]<next:정희>
 <prev:임정>[정희]<next:지웅>
 <prev:정희>[지웅]<next:null>

 > 수미 전에 영이 추가
 <prev:null>[철수]<next:영이>
 <prev:철수>[영이]<next:수미>
 <prev:영이>[수미]<next:임정>
 <prev:수미>[임정]<next:정희>
 <prev:임정>[정희]<next:지웅>
 <prev:정희>[지웅]<next:null>

 > 정희 이탈
 <prev:null>[철수]<next:영이>
 <prev:철수>[영이]<next:수미>
 <prev:영이>[수미]<next:임정>
 <prev:수미>[임정]<next:지웅>
 <prev:임정>[지웅]<next:null>

 */

 

 

---

 

 

• 이중 연결 리스트 탐색 예제
  • findNodeFromHead 메서드와 findNodeFromTail 메서드 추가 
  • findNodeFromHead 메서드는 노드 앞에서 부터 탐색 시작
  • findNodeFromTail 메서드는 노드 뒤에서 부터 탐색 시작

 

package linkedlist;

public class DoubleLinkedListTest {
    public static class Node<T> {
        T data;

        Node<T> prev = null;
        Node<T> next = null;

        public Node(T data) {
            this.data = data;
        }
    }

    public static class DoubleLinkedList<T> {
        public Node<T> head = null; // 첫번째 노드
        public Node<T> tail = null; // 마지막 노드

        public void addNode(T data) {
            if (head == null) {
                head = new Node<T>(data);
                tail = head;
            } else {
                Node<T> node = this.head;
                while (node.next != null) {
                    node = node.next;
                }

                node.next = new Node<T>(data);
                node.next.prev = node;
                this.tail = node.next;
            }
        }

        public void printAll() {
            if (head != null) {
                Node<T> node = this.head;
                printNode(node);
                while (node.next != null) {
                    node = node.next;
                    printNode(node);
                }
                System.out.println();
            }
        }

        private void printNode(Node<T> node) {
            if (node.prev != null)
                System.out.print("<prev:" + node.prev.data + ">");
            else
                System.out.print("<prev:" + null + ">");
            System.out.print("[" + node.data + "]");
            if (node.next != null)
                System.out.println("<next:" + node.next.data + ">");
            else
                System.out.println("<next:" + null + ">");
        }


        /**
         * 특정 노드 앞에 신규 노드 추가
         *
         * @param existedData : 기존 노드
         * @param addData     : 신규 노드
         * @return
         */
        public boolean insertToFront(T existedData, T addData) {
            if (this.head == null) {
                this.head = new Node<T>(addData);
                this.tail = this.head;
            } else if (this.head.data == existedData) {
                Node<T> newHead = new Node<T>(addData);
                newHead.next = this.head;
                this.head = newHead;
                return true;
            } else {
                Node<T> node = this.head;
                while (node != null) {
                    if (node.data == existedData) {
                        Node<T> nodePrev = node.prev;
                        nodePrev.next = new Node<T>(addData);
                        nodePrev.next.next = node;
                        nodePrev.next.prev = nodePrev;
                        node.prev = nodePrev.next;
                        return true;
                    } else {
                        node = node.next;
                    }
                }
            }
            return false;
        }

        private Node<T> findNodeFromHead(T data) {
            if (head != null) {
                Node<T> node = this.head;
                while (node != null) {
                    if (node.data.equals(data))
                        return node;
                    else
                        node = node.next; //앞에서 뒤로 이동
                }
            }
            return null;
        }

        private Node<T> findNodeFromTail(T data) {
            if (head != null) {
                Node<T> node = this.tail;
                while (node != null) {
                    if (node.data.equals(data))
                        return node;
                    else
                        node = node.prev; // 뒤에서 앞으로 이동
                }
            }
            return null;
        }


        public boolean removeNode(T data) {
            if (head != null) {
                Node<T> node = head;
                if (node.data == data) {
                    this.head = this.head.next;
                    return true;
                } else {
                    while (node.next != null) {
                        if (node.next.data == data) {
                            node.next = node.next.next;
                            node.next.prev = node;
                            return true;
                        }
                        node = node.next;
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        //findNodeFromHead, findNodeFromTail test
        System.out.println("\n> findNodeFromHead test 시작");
        // 노드 추가 시작 시간 기록
        long startTime = System.currentTimeMillis();

        DoubleLinkedList<Integer> findNodeList = new DoubleLinkedList<>();
        for (int i = 0; i < 200000; i++) {
            findNodeList.addNode(i);
        }
        //노드 추가 경과 시간 기록
        long endTime = System.currentTimeMillis();

        //노드 추가 경과 시간 계산
        long elapsedTime = (endTime - startTime) / 1000;
        System.out.println("노드 추가 경과 시간 : " + elapsedTime + "초");

        startTime = System.currentTimeMillis();
        Node<Integer> node = findNodeList.findNodeFromHead(199999);
        findNodeList.printNode(node);

        //탐색 종료 시간 기록
        endTime = System.currentTimeMillis();

        //탐색 경과 시간 계산
        double elapsedTime2 = (endTime - startTime) / 1000D;

        //결과 출력
        System.out.println("findNodeFromHead 탐색 실행 시간 : " + elapsedTime2 + "초");

        System.out.println("\n> findNodeFromTail test 시작");

        startTime = System.currentTimeMillis();
        node = findNodeList.findNodeFromTail(199999);
        findNodeList.printNode(node);

        //탐색 종료 시간 기록
        endTime = System.currentTimeMillis();

        //탐색 경과 시간 계산
        elapsedTime2 = (endTime - startTime) / 1000D;

        //결과 출력
        System.out.println("findNodeFromTail 탐색 실행 시간 : " + elapsedTime2 + "초");

    }
}

/**
 * [결과 값]

 > findNodeFromHead test 시작
 노드 추가 경과 시간 : 34초
 <prev:199998>[199999]<next:null>
 findNodeFromHead 탐색 실행 시간 : 0.002초

 > findNodeFromTail test 시작
 <prev:199998>[199999]<next:null>
 findNodeFromTail 탐색 실행 시간 : 0.0초

 */