[자료구조] 이중연결리스트 (Doubly Linked List)

yeonhwan619·2023년 8월 25일
자료구조

자료구조

목록 보기
2/6

이중 연결리스트란?

이중 연결리스트란 단일 연결리스트가 확장되어 Node들을 단방향이아닌 양방향으로 연결시킬 수 있도록 하여 이전, 다음 Node들을 추적할 수 있도록 만든 자료구조이다. 단일 연결리스트의 Node 가 value, next를 프로퍼티만을 가지고 있었던 것과는 다르게 이중 연결리스트는 여기에 prev라는 프로퍼티를 추가해 이전 Node의 참조값또한 지니고 있도록 한다.

이중 연결리스트 또한 연결리스트의 한 종류이기 때문에 많은 특징들을 단일 연결리스트와 공유한다.

이전 연결리스트 자료구조는 다음과 같은 프로퍼티를 가지고 있다.

  1. head : 이중 연결리스트의 가장 첫 번째 프로퍼티
  2. tail : 이중 연결리스트의 가장 마지막 프로퍼티
  3. length : 이중 연결리스트의 길이

이중 연결리스트 만들기

단일 연결리스트와 동일하게 Node를 먼저 생성한 후, 이들을 차례로 연결한 후에 이중 연결리스트를 통해 저장하도록 한다. 단, 이때 이중 연결리스트의 Node의 prev 프로퍼티에 이전 Node와의 연결도 포함시켜주어야 한다.

class Node {
	constructor(value, prev=null, next=null) {
    	this.value = value;
      	this.prev = prev;
      	this.next = next;
    }

}


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

}

const Node1 = new Node("a");
const Node2 = new Node("b", Node1);
const Node3 = new Node("c", Node2);

Node1.next = Node2;
Node2.next = Node3;

// a <-> b <-> c

const DLL = new DoublyLinkedList(Node1, Node3, 3);
// {head: Node1, tail: Node3, length: 3}

이중 연결리스트의 메소드

이중 연결리스트의 메소드는 단일 연결리스트의 메소드와 거의 동일하지만, prev 프로퍼티를 통해 조금 더 편리하게 순회할 수 있다는 점이 다르다. 살펴보게 될 이중 연결리스트의 메소드들은 다음과 같다.

  1. push : 연결리스트의 마지막에 Node를 추가한다.
  2. pop : 연결리스트의 마지막 Node를 제거한다.
  3. shift : 연결리스트의 첫부분에 Node를 제거한다.
  4. unshift : 연결리스트의 첫부분의 Node를 추가한다.
  5. get : 원하는 위치의 Node의 값을 얻는다.
  6. set : 원하는 위치의 Node의 값을 변경한다.
  7. insert : 원하는 위치에 Node를 삽입한다.
  8. remove : 원하는 위치의 Node를 제거한다.

(traverse는 단일 연결리스트와 동일하며, prev로 연결되었기 때문에 reverse 메소드를 구현할 필요가 없다)



1. push(value)

단일 연결리스트의 push 메소드와 동일한 역할을 한다. 다만 이 때 새롭게 추가되는 Node의 prev 프로퍼티 또한 적절하게 추가해주어야 한다.

1. value: Node의 값
return : 새롭게 추가한 Node

// 1. 리스트가 비어있을 때
// 2. 리스트가 비어있지 않을 때

push(value) {
	const newNode = new Node(value);
  	// 1)
  	if(!this.tail) {
    	this.head = newNode;
      	this.tail = newNode;
      	this.length++;
      	return newNode;
    }
  	// 2)
  	  this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
  	  this.length++;
  	  return newNode;
}


... 

DLL.push("d");
// {value: "d", prev: Node3, next: null}
// {head: Node1, tail: newNode, length: 4}
// a <-> b <-> c <-> d

2. pop

이중 연결리스트의 마지막에 위치한 Node를 제거하고 그 Node를 반환하는 메소드이다. 단일 연결리스트와는 다르게 제거한 Node의 prev 연결을 끊어주지 않는다면 마지막 Node에서 이전 값을 참조할 수 있다.

return : 제거된 Node

// 1. 리스트가 비었을 때
// 2. Node가 하나일 때
// 3. Node가 다수일 때

pop() {
  	// 1)
 	if(!this.tail || !this.head) return null;
  	
    // 2)
    if(this.length === 1) {
    	const temp = this.tail;
      	this.head = null;
      	this.tail = null;
      	this.length--;
      	return temp;
    }
  	
  	// 3)
	const temp = this.tail;
  	this.tail = this.tail.prev;
  	this.tail.next = null;
  	temp.prev = null;
  	this.length--;
  	return temp;
}

...

DLL.pop();
// {value: "c", next: null, prev: null}
// {head: Node1, tail: Node2, length: 2}
// a <-> b

3. shift

이중 연결리스트의 첫 번째 부분에서 Node를 하나 제거한후 그 값을 반환한다. 단일 연결리스트와 다르게 제거한 후 prev 연결 또한 재조정 해주어야 한다.

return: 제거한 Node

// 1. 리스트가 비었을 때
// 2. Node가 하나일 때
// 3. Node가 다수일 때

shift() {
  	// 1)
  	if(!this.head || !this.tail) return null;
  	// 2)
  	if(this.length === 1) {
      	const temp = this.head;
    	this.head = null;
      	this.tail = null;
      	this.length--;
      	return temp;
    }
  	// 3)
	const temp = this.head;
  	this.head = this.head.next;
  	this.head.prev = null;
  	temp.next = null;
  	this.length--;

}

...


DLL.shift();
// {value: "a", next: null, prev: null} 
// {head: Node2, tail: Node3, length: 2}
// b <-> c

4. unshift(value)

이중 연결리스트의 첫 부분에 value값을 가지는 새로운 Node를 생성하고 추가한다. 역시 이전의 존재하던 Node의 prev연결을 재조정해주어야한다.

1. value: 새로운 Node의 값
return: 새롭게 생성된 Node

// 1. 리스트가 비어있을 때
// 2. 리스트가 비어있지 않을 때
unshift(value) {
	const newNode = new Node(value);
  	// 1)
  	if(!this.head || !this.tail) {
    	this.head = newNode;
      	this.tail = newNode;
      	this.length++;
      	return newNode;
    }
  	// 2)
	newNode.next = this.head;
  	this.head.prev = newNode;
    this.head = newNode;
  	this.length++:
    return newNode;
}

...

DLL.unshift("z");
// {value: "z", next: Node1, prev:null}
// {head: newNode, tail: Node3, length: 4}
// z <-> a <-> b <-> c

5. get(index)

원하는 index를 전달 받아 해당 위치에 존재하는 Node를 반환하도록 한다. 순회해서 값을 찾아야 한 다는 점은 동일하지만 이중 연결리스트는 prev 라는 프로퍼티를 가지고 있기 때문에 이진 탐색을 통해서 순회하는 과정을 보다 최적화 할 수 있다.

1. index : 찾길 원하는 Node의 index
return : 찾아낸 Node 

// 1) 리스트가 비었을 때
// 2) index 가 tail에 가까울 때
// 3) index 가 head에 가까울 때

get(index) {
  	// 1)
	if(index < 0 || index >=this.length) return null;
  	
  	// 2)
	if(index >= this.length / 2) {
    	let count = this.length - 1;
      	let foundNode = this.tail;
      	while(count > index) {
        	foundNode = foundNode.prev;
          	count--;
        }
      	return foundNode;
    }
  	
  	// 3)
  	let count = 0;
  	let foundNode = this.head;
  	while(count < index) {
    	foundNode = foundNode.next;
      	count++;
    }
  	return foundNode;
}


...

DLL.get(2);
// {value: "b", next: Node3}
// a <-> b <-> c

6. set(index, value)

해당 index에 존재하는 Node의 값을 value로 변경한다. 단일 연결리스트와 동일하게 미리 작성해두었던 get 메소드를 통해서 쉽게 변경할 수 있다.

1. index : 변경할 위치 index
2. value : 변경할 값
return : 변경된 Node

// 1. Node가 존재할 경우
// 2. Node가 존재하지 않을 경우

set(index, value) {
	const foundNode = this.get(index);
  	// 1)
  	if(foundNode) foundNode.value = value;
	// 2)
  return foundNode;
}

... 

DLL.set(2, "B");
// {value: "B", next: Node3, prev: Node1}
// a <-> B <-> c

7. insert(index, value)

해당 index에 value를 값으로 가진 Node를 새로 생성해 삽입한다. 미리 작성해두었던 push, unshift, get 메소드를 통해서 쉽게 삽입할 수 있다. 단, 새로운 위치에 Node를 삽입 할때 앞 뒤의 prev, next 프로퍼티를 적절히 할당 해주어야 한다.

1. index: 삽입할 위치
2. value: 새롭게 생성할 Node의 값
return : 새롭게 생성된 Node

// 1. index가 0일 때
// 2. index가 length 일 때
// 3. index가 0~length 사이 일 때
insert(index, value) {
	if(index < 0 || index > this.length) return null;
  	
  	// 1)
  	if(index === 0) this.unshift(value);
  	// 2)
  	if(index === this.length) this.push(value);
  	
  	// 3)
  	const beforeIndexNode = this.get(index - 1);
  	const newNode = new Node(value);
  	// 삽입 위치 이전 노드 -> 새로운 노드 -> 삽입 위치 이전의 원래 다음 노드
  	[beforeIndexNode.next, newNode.next] = [newNode, beforeIndexNode.next ];
  	// 삽입 위치 이전 노드 <- 새로운 노드 <- 삽입 위치 이전의 원래 다음 노드
  	[newNode.prev, beforeIndexNode.next.prev] = [beforeIndexNode, newNode];
  	this.length++:
    return newNode;
}

...
DLL.insert("ㄱ", 1);
// {value: "ㄱ", next: Node2, prev: Node1}
// a<-> ㄱ <-> b <-> c

8.remove(index)

해당 index에 위치한 Node를 제거하고 제거한 Node를 반환한다. insert와 마찬 가지로 중간 위치에서 Node를 제거할 때 next, prev 프로퍼티의 연결을 적절히 변경해주어야 한다.

1. index: 제거할 Node의 위치
return : 제거한 Node

// 1. index가 0일 때
// 2. index가 length 일 때
// 3. index가 0~length 사이 일 때
remove(index) {
  
	if(index < 0 || index > this.length) return null;
    // 1)	
    if(index === 0) this.shift();
    // 2)
  	if(index === this.length - 1) this.pop();
    // 3)
  	const indexNode = this.found(index);
  	// 인덱스 이전 노드 <-> 인덱스 다음 노드
  	[indexNode.prev.next, indexNode.next.prev]= [indexNode.next, indexNode.prev];
  	indexNode.prev = null;
  	indexNode.next = null;
  	this.length--;
  	return indexNode;

}

DLL.remove(1);
// {value: "b", next: null, prev: null}
// a <-> c


이중 연결리스트의 Big O

삽입(insertion) : O(1)
데이터를 삽입하는데 탐색을 필요로 하지 않는다. (리스트의 중간의 경우 제외)

제거(removal) : O(1)
데이터를 제거하는데 탐색을 필요로 하지 않는다. 단일 연결리스트와 다르게 tail에서 데이터를 제거하는 경우도 문제가 되지 않는다.(리스트의 중간의 경우 제외)

탐색(searching) : O(N)
리스트를 탐색하기 위해서는 연결을 따라 순회하여야 하기 때문에 O(N)만큼 시간이 필요하게 된다.

접근(accessing) : O(N)
어떠한 값에 접근하기 위해서는 연결을 따라 순회하여야 하기 때문에 O(N)만큼 시간이 필요하게 된다.

profile
이전 포스트

[자료구조] 단일 연결리스트 (Singly Linked List)

다음 포스트

[자료구조] 큐 (Queue) / 스택 (Stack)

4개의 댓글

comment-user-thumbnail
김일태
2023년 9월 10일

단일 연결리스트랑 방향성의 차이가 있군여 !!

답글 달기
comment-user-thumbnail
윤뿔소
2023년 9월 10일

단일 보다 더 복잡해졌네요,, 뭔가 뷰가 떠오르는 구조 같기도 합니다 잘보고 갑니다 ㅎㅎ

답글 달기
comment-user-thumbnail
김소라
2023년 9월 10일

단일 연결보고 그다음에 봐서 그런지 좀더 쉽게 읽히는거 같습니다 ㅎㅎ 잘보고갑니다!

답글 달기
comment-user-thumbnail
지은
2023년 9월 10일

단일 연결 리스트와 다르게 뒤에서 값을 제거하는 경우 O(1)의 시간복잡도를 갖는군요!
그래서 값을 삽입/삭제하고 작업이 빈번할 때는 이중연결리스트를 사용하는 게 좋다고 하네요. 정리 잘 읽었습니다 😄

답글 달기