ALGORITHM/Theory

Doubly Linked List - 이중 연결 리스트

Harimad 2022. 5. 18. 15:45

목차

더보기
1. 이중 연결 리스트 소개
2. Node class 셋업하기
3. Push 메소드
4. Push 메소드 솔루션
5. Pop 메소드
6. Pop 메소드 솔루션
7. Shift 메소드
8. Shift 메소드 솔루션
9. Unshift 메소드
10. Unshift 메소드 솔루션
11. Get 메소드
12. Get 메소드 솔루션
13. Set 메소드
14. Set 메소드 솔루션
15. Insert 메소드
16. Insert 메소드 솔루션
17. Remove 메소드
18. Remove 메소드 솔루션
19. 단일 연결 리스트와 이중 연결 리스트 비교

 

1. 이중 연결리스트 소개

 

VisuAlgo

슬라이드

 

최종

더보기 
class Node{
    constructor(val){
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}


class DoublyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(this.length === 0){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return this;
    } 
    pop(){
        if(!this.head) return undefined;
        var poppedNode = this.tail;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
    shift(){
        if(this.length === 0) return undefined;
        var oldHead = this.head;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        }else{
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var count, current;
        if(index <= this.length/2){
            count = 0;
            current = this.head;
            while(count !== index){
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            while(count !== index){
                current = current.prev;
                count--;
            }
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode != null){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);

        var newNode = new Node(val);
        var beforeNode = this.get(index-1);
        var afterNode = beforeNode.next;
        
        beforeNode.next = newNode, newNode.prev = beforeNode;
        newNode.next = afterNode, afterNode.prev = newNode;
        this.length++;
        return true;
    }
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) return this.shift();
        if (index === this.length-1) return this.pop();
        
        var removedNode = this.get(index);
        var beforeNode = removedNode.prev;
        var afterNode = removedNode.next;
        
        beforeNode.next = afterNode;
        afterNode.prev = beforeNode;
        
        removedNode.next = null;
        removedNode.prev = null;
        this.length--;
        return removedNode;
    }
    reverse() {
        var node = this.head;
        this.head = this.tail;
        this.tail = node;
        
        var next;
        var prev = null;
        
        for (let i = 0; i < this.length; i++) {
            next = node.next;
            node.next = prev;
            node.prev = next;
            prev = node;
            node = next;
        }
    return this;
    }
    print() {
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
    console.log(arr);
    }
}

var list = new DoublyLinkedList()
list.push("Harry")
list.push("Ron")
list.push("Hermione")

2. Node class 셋업하기

//DLL_Classes.js
class Node{
    constructor(val){
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

 

3. Push 메소드

push 의사코드

1. 추가할 노드 생성 (값을 가지는 새 노드 생성)

2. head가 null인지 길이가 0인지 확인 (기본적으로 리스트가 비어 있나 확인)

  2-1. 만약 그렇다면, head와 tail 모두가 새로 만든 노드로 설정

  2-2. 그 외에는 아무것도 할 필요가 없음 (prev나 next로 연결할 요소가 존재X 때문)

3. 그렇지 않고, 리스트에 무언가 있다면, 현재 tail을 찾아서 tail의 next 프로퍼티를 새로 만든 노드로 설정 (→)

4. 그리고 새로 만든 노드의 prev 프로퍼티를 예전 tail로 설정 (반대방향으로도 화살표 만듦) (←)

5. tail 프로퍼티를 가장 끝에 있게 된 새로운 노드로 바꿈

6. 길이 1 증가

7. Doubly Linked List(이중 연결 리스트) 반환

 

4. Push 메소드 솔루션

class DoublyLinkedList {
    // ...
    push(val){
        var newNode = new Node(val);
        if(this.length === 0){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}

예시)

oldNode		newNode 
-----------------------
Head
99	-> 	100

	<-
    		Tail

5. Pop 메소드

pop 의사코드

1. head가 없다면, undefined 리턴

2. 현재 tail을 변수로 저장, 나중에 리턴

3. 만약에 길이가 1이라면, head와 tail을 null로 설정

4. tail을 그 전에 있는 노드가 되도록 업데이트 (이제 tail이 이전 tail의 prev에 있는 node가 됨)

5. 새로운 tail의 next를 null로 설정

6. 길이를 1 감소

7. 제거된 값(2번) 리턴

 

6. Pop 메소드 솔루션

class DoublyLinkedList {
    // ...
    pop(){
        if(!this.head) return undefined;
        var poppedNode = this.tail;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
}

 

7. Shift 메소드

shift 의사코드

1. 만약 길이가 0이면, undefined 리턴

2. 현재 head 프로퍼티를 변수에 저장 (옛 head라 지칭), 나중에 리턴

3. 길이가 1이라면, head와 tail을 각각 null로 설정

4. head를 2번의 옛 head의 next로 업데이트

5. head의 prev 프로퍼티를 null로 설정

6. 옛 head의 next를 null로 설정

7. 길이 1 감소

8. 옛 head 리턴

 

8. Shift 메소드 솔루션

class DoublyLinkedList {
    // ...
    shift(){
        if(this.length === 0) return undefined;
        var oldHead = this.head;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        }else{
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }
}

실행순서

--------Original--------------------------------------
100	↔	200	↔	300
Head				Tail
--------Step1-----------------------------------------
100	↔	200	↔	300
		Head
--------Step2-----------------------------------------
null	←	200	↔	300
		Head
--------Step3-----------------------------------------
100	→	null

 

9. Unshift 메소드

unshift 의사코드

1. 입력된 값을 가지는 새 노드 생성

2. 길이가 0이라면,

  2-1. 새 노드를 head와 tail로 설정

3. 그렇지 않으면, 

  3-1. head의 prev 프로퍼티를 새 노드로 설정

  3-2. 새 노드의 next 프로퍼티를 head 프로퍼티로 설정

  3-3. head를 새 노드로 업데이트

4. 길이 1 증가

5. list 리턴

 

10. Unshift 메소드 솔루션

class DoublyLinkedList {
    // ...
    unshift(val){
        var newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

 

11. Get 메소드

get 의사코드

1. (index 유효성 검사) 만약에 index가 0보다 작거나 리스트 길이보다 크거나 같을 때, null 리턴

(10개 요소있다면 index 10번 없음, 가장 큰 값은 9임)

2. 만약에 index가 리스트의 길이의 절반보다 같거나 작다면, (길이를 2로 나눈 다음 그 결과와 index를 비교)

  2-1. 리스트의 시작 지점부터 루프를 돌리며 노드를 찾음

3. 2가 거짓이라면 (리스트 길이 절반보다 크다면),

  3-1. 리스트의 끝 지점부터 루프를 도릴며 노드를 찾음

 

12. Get 메소드 솔루션

class DoublyLinkedList {
    // ...
    get(index){
        if(index < 0 || index >= this.length) return null;
        var count, current;
        if(index <= this.length/2){
            count = 0;
            current = this.head;
            while(count !== index){
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            while(count !== index){
                current = current.prev;
                count--;
            }
        }
        return current;
    }
}

 

13. Set 메소드

set 의사코드

1. 함수에 입력된 index 값을 넣은 get 메소드의 결과값을 받는 변수를 만듦

  1-1. (get이 이미 index 유효성 판단 해줌) get 메서드가 유효한 노드를 리턴하면, 그 노드에 전달 받은 값으로 설정

  1-2. true 리턴

2. 그렇지 않으면, false 리턴

14. Set 메소드 솔루션

class DoublyLinkedList {
    // ...
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode != null){
            foundNode.val = val;
            return true;
        }
        return false;
    }
}

15. Insert 메소드

insert 의사코드

1. (index 유효성 검사) index가 0보다 작거나 리스트 길이보다 크거나 같을 때 false 리턴

2. index가 0이면, unshift

3. index가 리스트 길이와 같다면, push

4. 그렇지 않다면, get 메소드를 사용해서 index-1에 접근

5. next와 prev 프로퍼티를 이용해서 노드들을 잘 연결

  (beforeNode ↔ afterNode) → (beforeNode ↔ newNode ↔ afterNode)

6. 길이 1 증가

7. true 리턴

16. Insert 메소드 솔루션

class DoublyLinkedList {
    // ...
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);

        var newNode = new Node(val);
        var beforeNode = this.get(index-1);
        var afterNode = beforeNode.next;
        
        beforeNode.next = newNode, newNode.prev = beforeNode;
        newNode.next = afterNode, afterNode.prev = newNode;
        this.length++;
        return true;
    }
}

17. Remove 메소드

remove 의사코드

1. (index 유효성 확인) index가 0보다 작거나 리스트 길이보다 크거나 같으면, undefined 리턴

2. index가 0이면, shift

3. index가 리스트 길이-1이면, pop

4. get 메서드를 이용해서 제거해야 할 요소 찾음

5. next와 prev 프로퍼티를 바꿔서 제대로 제거해줌 (구멍메꾸기)

6. 4번에서 찾은 노드의 next와 prev를 null로 설정 (제거할 노드 미아 만들기)

7. 길이 1 감소

8. 제거할 노드 리턴

 

ex) 100 ↔ 200 ↔ 300

Q. 200제거?

① get으로 100 찾기

② 100 ↔ 300 연결

③ 200 :  prev = null & next = null

④ 200 리턴!

 

18. Remove 메소드 솔루션

class DoublyLinkedList {
    // ...
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) return this.shift();
        if (index === this.length-1) return this.pop();
        
        var removedNode = this.get(index);
        var beforeNode = removedNode.prev;
        var afterNode = removedNode.next;
        
        beforeNode.next = afterNode;
        afterNode.prev = beforeNode;
        
        removedNode.next = null;
        removedNode.prev = null;
        this.length--;
        return removedNode;
    }
}

 

19. 단일 연결 리스트와 이중 연결 리스트 비교

이중 연결 리스트의 Big O

Insertion - O(1)

Removal - O(1)

Searching - O(N) (원랜 O(N / 2))

Access - O(N)

 

회고

  • 이중 연결 리스트는 그 전에 있는 노드를 가리키는 포인터가 하나 더 있다는 점만 빼면 단일 연결 리스트와 똑같다.
  • 이중 연결 리스트는 무언가를 찾는데 더 나은 성능을 발휘한다. 왜냐하면 절반의 시간만 걸리기 때문이다.
  • 그렇지만, 추가로 만든 포인터는 메모리를 더 소모하므로 약점이 되기도 한다
저작자표시 비영리 변경금지 (새창열림)