[LinkedList][Java] 단일 연결리스트 vs 이중 연결리스트

항해99 스터디 도중 나에겐 생소한 Single LinkedList 개념만 등장하길래 Double LInkedList 개념 복습겸 정리와 비교

LinkedList 알아보기

1. 단일 연결 리스트 (Singly Linked List): 단일 연결 리스트는 각 노드가 데이터 요소와 **다음 노드**를 가리키는 포인터로 이루어진 구조입니다. 이것은 **한 방향**으로만 탐색할 수 있는 구조이며, 첫 번째 노드에서 시작하여 다음 노드로 이동합니다.
2. **Tail에서 역방향 탐색은 안되지만 추가에 용이하도록 Tail을 들고 있을 수는 있음
3. 이중 연결 리스트 (Doubly Linked List): 이중 연결 리스트는 각 노드가 **이전 노드**와 **다음 노드**를 가리키는 포인터를 가지는 구조입니다. 이로 인해 **양쪽 방향**으로 탐색이 가능하며, 양방향으로 요소를 삽입하거나 삭제할 수 있습니다.
4. 원형 연결 리스트 (Circular Linked List): 원형 연결 리스트는 단일 또는 이중 연결 리스트의 변형으로, 마지막 노드가 첫 번째 노드를 가리키는 원형 구조를 갖습니다. 이를 통해 끝과 시작 지점이 연결되어 있어 순환적인 데이터 구조를 형성합니다.
5. 이중 연결 리스트의 확장 (Doubly Linked List with Sentinel): 이중 연결 리스트에 더해 헤드와 테일을 나타내는 더미(dummy) 노드를 추가하여 리스트의 시작과 끝을 더 간단하게 관리할 수 있게 해줍니다.

 

 

 

Single Linked List와 비교했을 때

• 단점 : Single Linked List를 사용해도 풀 수 있는 문제의 경우 Single LinkedList보다 느린 속도
• 오늘 같은 예제의 경우 Single Linked List로 충분히 풀 수 있었으므로 노드 연결에 2배의 시간이 걸리는 Doubly Linked List 사용 시 **Single Linked List**보다 느렸을 것,
• 장점 : 뒤 쪽의 요소를 제거할 때 더 빠르도록 구현할 수 있다.
• 제거하려는 index가 head 보다 tail에 가까울 때, tail에서 출발하도록 할 수 있다.

 

Array vs Single LinkedList vs Double LinkedList

배열과 Single Linked List Double Linked list 시간복잡도 비교

 

** : 평균은 그보다 빠를 것

Node 정의의 비교

# java Double Linked List
static class Node{
    Node left;
    Node right;
    int value;
    public Node(int value){
        this.value = value;
    }
}

 # python Single Linked List
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

 

 

클래스 변수 비교와  요소 추가 함수 비교

// Java
static class DoubleLinkedList{
    Node head;
    Node tail;
    int size;
    public DoubleLinkedList(){
        this.size = 0;
    }
    
    public void addBack(int value){ // 맨 뒤에 추가
        Node addNode = new Node(value); // 추가할 노드
        if(isEmpty()){ // 빈 링크드 리스트라면 head & tail로 지정
            this.head = addNode;
            this.tail = addNode;
            return;
        }

        Node node = tail; // 끝의 노드에 바로 접근
        // 추가할노드와 원래 tail 노드를 서로 연결
        node.right = addNode;
        addNode.left = node;
        this.tail = addNode; // 추가된 노드를 tail로 지정
        //size 증가 처리
        this.size++;
    }
}

 

# python
class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val): # 맨 뒤에 추가
        
				if not self.head: #빈 링크드리스트라면 head 로 지정
            self.head = ListNode(val, None)
            return

        node = self.head # 헤드 노드에서부터 출발
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

 

DoubleLinkedList 는 head에 이어 tail 변수를 들고 있어 맨 뒤에 바로 접근할 수 있다.

물론 Single LinkedList를 tail 변수를 들고 맨 뒤의 원소에 접근할 수 있도록 할 수도 있지만, 극적인 비교를 위해서 tail을 모른다고 가정하고 add 함수를 비교해 보았다.

SingleLinkedList는 while문을 활용하여 head에서부터 계속해서 다음 노드로 포인터를 옮겨가며 탐색해야하는 번거로움이 있다.

 

 

 

java 코드 전문

직접 구현해본 Double Linked List 전문

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 이중연결리스트 {
    static class Node{
        Node left;
        Node right;
        int value;
        public Node(int value){
            this.value = value;
        }
    }

    static class DoubleLinkedList{
        Node head;
        Node tail;
        int size;
        public DoubleLinkedList(){
            this.size = 0;
        }
        public int size(){
            return this.size;
        }
        public void print(){
            sb.setLength(0);
            Node node = this.head;
            while(node != null){
                sb.append(node.value).append(' ');
                node = node.right;
            }
            sb.append('\\n');
            이중연결리스트.print();
        }
        public void addBack(int value){
            Node addNode = new Node(value); // 추가할 노드
            if(isEmpty()){
                this.head = addNode;
                this.tail = addNode;
                return;
            }

            Node node = tail; // 끝의 노드에 바로 접근

            // 추가할노드와 원래 tail 노드를 서로 연결
            node.right = addNode;
            addNode.left = node;
            this.tail = addNode; // 추가된 노드를 tail로 지정
            //size 증가 처리
            this.size++;
        }
        public void addFront(int value){
            Node addNode = new Node(value);
            if(isEmpty()){
                this.head = addNode;
                this.tail = addNode;
                return;
            }

            Node node = head; // 맨앞의 노드에 바로 접근

            node.left = addNode;
            addNode.right = node;
            this.head = addNode; // 추가된 노드를 head로 지정

            //size 증가 처리
            this.size++;
        }
        public boolean isEmpty(){
            if(this.head == null)
                return true;
            return false;
        }

        public void delete(int index){
            if(isEmpty())
                return;
            if(this.size <= index)
                return;

            Node node = null;

            if(index < this.size / 2){ // 앞에서 부터 지우는 게 유리하다
                node = head;
                while(index > 0 && node.right != null){
                    node = node.right;
                    index --;
                }
            }
            else if(index >= this.size / 2){ // 뒤에서 부터 지우는 게 유리하다
                node = tail;
                while(index <size && node.left != null){
                    node = node.left;
                    index ++;
                }
            }
            // 지울 노드
            if(node == head){
                node.right.left = null;
                this.head = node.right;
            }
            else if(node == tail){
                node.left.right = null;
                this.tail = node.left;
            }
            else{
                node.left.right = node.right;
                node.right.left = node.left;
            }
            // size 감소 처리
            this.size --;
        }
    }
    static void input() throws Exception {
        DoubleLinkedList ddl = new DoubleLinkedList();
        int cases = scan.nextInt();
        for(int i = 0; i < cases; i++){
            int operation = scan.nextInt(); // 1 : addFront  2 : addBack 0 : delete
            int num = scan.nextInt();
            if(operation == 1){
                ddl.addFront(num);
            } else if (operation==2) {
                ddl.addBack(num);
            }
            else if(operation == 0){
                ddl.delete(num);
            }
            ddl.print();
        }
    }

    static void print(){
        System.out.print(sb.toString());
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

}

테스트 케이스

15
1 10
1 9
2 181
2 32
2 84
1 29
0 0
0 1
1 123
1 123
1 42
2 100000
0 8
0 5
0 5
2 0

15개의 {명령어 숫자(인덱스)} 로 이루어진 테스트 케이스 입력에 대해서

{명령어 숫자(인덱스)}

{명령어 숫자(인덱스)}

{명령어 숫자(인덱스)}

위와 같은 형태로 입력을 받고있으며, 첫번 째 케이스는 명령어 : 1 과 숫자(인덱스) : 10 을 입력받았다.

각 명령어는

1 : 맨 앞에 추가하기

2 : 맨 뒤에 추가하기

0 : 해당하는 인덱스 삭제

를 의미하며

 

 

실행 결과는 다음과 같다.

1 10			10
1 9			9 10
2 181			9 10 181
2 32			9 10 181 32
2 84			9 10 181 32 84
1 29			29 9 10 181 32 84
0 0			9 10 181 32 84
0 1			9 181 32 84
1 123		 	123 9 181 32 84
1 123			123 123 9 181 32 84
1 42			42 123 123 9 181 32 84
2 100000		42 123 123 9 181 32 84 100000
0 8			42 123 123 9 181 32 84 100000
0 5			42 123 123 9 181 84 100000
0 5		  	42 123 123 9 181 100000