자료구조 정리3: Doubly Linked Lists

이중 연결 리스트

단방향 연결 리스트에서 앞으로 갈수있는 포인터가 추가됨.

뒤에서 앞으로도 갈 수 있어서 편리하지만 그만큼 메모리를 더 사용한다.

포인터가 하나 추가된 것 말고는 단방향 연결 리스트와 동일. 인덱스 없음.

https://visualgo.net/en/list?slide=1

비주알고

구현

node 셋업

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()

맨 뒤에 새로운 값을 추가한 후, 포인터 두개를 모두 수정한다.

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;  // 현재 tail의 next를 새 노드로 한다
            newNode.prev = this.tail;  // 그리고 새 노드의 prev을 현재 tail로 한다.
            this.tail = newNode;     // tail을 새로 추가한 노드로 바꿈.
        }
        this.length++;
        return this;
    }
}

pop()

맨 뒤 엘리먼트를 삭제

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;  // tail을 없앨 노드의 앞 노드로 바꿈
            this.tail.next = null;       // tail의 next를 null로 바꿈(끝이니까)
            poppedNode.prev = null;      // 없앨 노드의 prev를 null로 바꿈(리스트에 끊어지니까)
        }
        this.length--;   // 길이를 1 줄임
        return poppedNode;  // 없앤 노드를 반환
    }

shift()

맨 앞 엘리먼트를 삭제

shift(){
        if(this.length === 0) return undefined; // 빈 리스트면
        var oldHead = this.head;   // 삭제할 노드를 현재의 head로.
        if(this.length === 1){  // 엘리먼트가 하나뿐인 리스트라면
            this.head = null;
            this.tail = null;
        }else{
            this.head = oldHead.next; // 새로운 head는 현재 헤드의 next
            this.head.prev = null;    // 새로운 head의 prev은 null로
            oldHead.next = null;   // 없앨 노드의 next는 null로(연결 끊음)
        }
        this.length--;  // 길이 1 줄이고
        return oldHead;  // 없앤 노드 반환
    }

unshift()

맨 앞에 새로운 노드 추가

unshift(val){
        var newNode = new Node(val);  // 새로운 노드를 만들고
        if(this.length === 0) {   // 빈 리스트라면 
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;  // 현재 헤드의 prev을 새 노드로
            newNode.next = this.head;  // 새 노드의 next를 현재의 헤드로
            this.head = newNode;  // 그리구서 head를 새 노드로 바꿈.
        }
        this.length++;  // 길이는 1 늘이고
        return this;  // this 반환.
    }

get()

인덱스를 인자로 받아 리스트에서 해당 위치의 노드를 반환.

단방향 연결 리스트의 get과 다른 점은 뒤에서부터 시작할수도 있다는 점.

get(index){
        if(index < 0 || index >= this.length) return null;  // 인덱스가 유효한지
        var count, current;
        if(index <= this.length/2){ // 만약 인덱스가 리스트 길이의 절반보다 작으면(앞에서부터)
            count = 0;  // 카운터를 선언하고
            current = this.head;  // head부터 시작해서
            while(count !== index){  // 해당 인덱스 도달할때까지 반복문
                current = current.next;
                count++;
            }
        } else {               // 인덱스가 리스트 길이의 절반보다 크면(뒤에서부터)
            count = this.length - 1;  // 카운터를 뒤에서부터
            current = this.tail;    // tail부터 시작
            while(count !== index){
                current = current.prev;   
                count--;   // 카운터를 1씩 빼면서 반복문
            }
        }
        return current;
    }

set()

인덱스와 값을 인자로 받아 해당 인덱스의 값을 바꾼다.

앞에서 만든 get을 이용한다.

set(index, val){
        var foundNode = this.get(index);  // get으로 해당 노드를 찾고
        if(foundNode != null){
            foundNode.val = val;  // 바꿈.
            return true;
        }
        return false;
    }

insert()

인덱스와 값을 받아 중간에 삽입한다

insert(index, val){
        if(index < 0 || index > this.length) return false; // 인덱스 유효한지
        if(index === 0) return !!this.unshift(val);  // 인덱스가 0이면 맨앞 unshift
        if(index === this.length) return !!this.push(val); // 맨뒤면 push

        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++;  // 길이를 1 늘이고
        return true;  // true를 리턴.
    }

remove()

인덱스를 받아 해당 인덱스의 노드를 제거.

remove(index) {
	if(index < 0 || index >= this.length) return undefined; // 인덱스 유효성 검사
	if(index === 0) return this.shift();  // 맨앞걸 제거한다면 shift
	if(index === this.length - 1) return this.pop();  //맨 뒤는 pop으로
	var removedNode = this.get(index);  //지울 노드는 get으로 찾음
	var beforeNode = removedNode.prev;  // 지울 노드의 앞칸 노드
	var afterNode = removedNode.next;  // 지울 노드의 뒷 노드
	beforeNode.next = afterNode;   // 앞칸 노드의 next를 뒷 노드로 바꿈
	afterNode.prev = beforeNode;   // 뒷칸 노드의 prev을 앞칸 노드로 바꿈
	removedNode.next = null;   // 지울 노드의 next와 prev을 모두 null로 바꿈(연결 끊기)
	removedNode.prev = null;
	this.length--;  // 길이를 1 줄이고
	return removedNode;  // 지운 노드를 반환
}

reverse()

리스트의 앞 뒤를 바꿈.

reverse() {
    let current = this.head;
    [this.head, this.tail] = [this.tail, this.head]; // 구조분해할당으로 head와 tail을 교체
 
    for (let i = 0; i < this.length; i++) {
      const { prev, next } = current; // current라는 객체의 property를 중괄호 구조분해할당으로 선언한다.
 
      current.prev = next;  // 현재 current의 prev을 위에 선언한 next로 바꾸고
      current.next = prev;  // next는 prev으로 바꾼다.
      current = next;  // 바꾼 후 current는 next로 바꿈.
    }
 
    return this;
  }

단방향 연결 리스트와 이중 연결 리스트 비교

Big-0

insertion - O(1)

removal - O(1)

searching - O(N)

access - O(N)

인덱스에 따라 처음에서 가까운지, 뒤에서 가까운지 비교하여 더 빠른 쪽을 선택할 수 있음.

데이터를 반대 방향을 취급해야 하는 경우라면,

예컨대 방문 페이지 리스트 같은 경우에는 앞으로 가기, 뒤로가기가 있으므로 이중 연결 리스트가 적합.

이중 연결 리스트는 무언가를 찾는데 더 나은 성능을 발휘한다.

하지만 포인터를 하나 추가함으로써 메모리를 더 사용한다.