[알고리즘👽] 14. 이중 연결 리스트

알고리즘

[알고리즘👽] 14. 이중 연결 리스트

머털박사 2022. 9. 18. 18:12

해당 포스팅은 알고리즘 이중 연결 리스트(Doubly Linked Lists)에 대해 다룹니다. Udemy JavsScript 알고리즘 & 자료구조 마스터 클래스를 공부하며 정리한 내용입니다.

이중 연결 리스트 소개

스포일러를 하자면, 우리가 할 일은 앞의 노드로 갈 수 있는 포인터를 하나 더하는 것 뿐이랍니다. 작은 차이 같지만 실제 코드를 작성할 때 많은 것이 바뀝니다.

<aside> 💡 목표

이중 연결 리스트 작성
이중 연결 리스트와 단일 연결 리스트 비교
이중 연결 리스트에 기본 함수 추가 </aside>

이중은 뭐가 다른가?

거의 단일 연결 리스트와 비슷하다. 다른 것은 포인터다. 뒤로 가는 포인터가 있다. 코드를 작성할 때 훨씬 더 복잡할 것이다.

단일 연결 리스트와 비교

More memory === More Flexibility

Node class 셋업하기

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 메소드

Pushing

이중 연결 리스트 끝에 node를 더한다

의사코드

추가할 노드를 만들기
헤드가 널인지 아니면 길이가 0인지 확인한다
리스트에 무언가 있다면, 현재 테일을 찾아서 테일의 next 프로퍼티를 우리가 만든 새로운 노드로 설정해줍니다.
새로 만든 노드의 prev 프로퍼티를 예전 테일로 설정해줍니다.
테일 프로퍼티를 이제 가장 끝에 있게 된 새로운 노드로 바꿔줍니다.
길이를 1 늘려주고 전체 리스트를 출력합니다.

Push 메소드 솔루션

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){
		if(this.length === 0){
			this.head = newNode;
			this.tail = newNode;
		} else{
			this.tail.next = newNode;
			nesNode.prev= this.tail;
			this.tail = newNode;
		}
		this.length++;
		return this;
	}
}

단일 리스트와 비슷하지만 next prev 둘 다 있어서 작업이 더 많다.

Pop 메소드

Poping

이중 연결 리시트 끝의 노드를 제거한다

의사코드

head가 없을시 undefined를 출력
현재 테일을 나중에 출력할 수 있도록 변수에 저장해 줍니다.
만약 길이가 0이라면, 헤드와 테일 둘 다 널로 설정한다.
이제 테일이 그 전에 있는 노드가 되도록 설정해줍니다.
새로운 테일의 next를 null로 설정한다
길이를 줄인다
제거된 값을 출력

Pop 메소드 솔루션

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;
	}
	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;
		}
		this.length--;
		return poppedNode;
	}
}

Shift 메소드

Shifitng

이중 연결 리스트 맨 앞의 노드를 제거한다

의사코드

길이가 0이면 undefined를 반환한다
현재 헤드 프로퍼티를 변수에 저장한다.
길이가 1이면 헤드와 테일을 null로 설정한다
헤드가 예전 헤드의 next가 되도록 업데이트한다.
헤드의 prev를 null로 설정
예전 헤드의 next를 null로 설정
길이를 줄이고
예전 헤드를 반환한다.

단일 연결 리스트와 같은데 prev만 신경쓰면 된다.

shift 메소드 솔루션

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;
	}
	shift() {
		if(this.length === 0) return undefined;
		var oldHead = this.head;
		if(this.length === 1){
			this.head = null;
			this.tail = null;
		}
			this.head = oldHead.next;
			this.head.prev= null;
			oldHead.next = null;
			this.length--;
			return oldHead;
	}
}

Unshift 메소드

Unshifting

이중 연결 리스트의 시작에 노드를 추가한다

의사코드

입력 값을 가지는 새로운 코드를 만들기
만약 길이가 0이라면
- 헤드와 테일을 새로운 노드로 생성한다.
그렇지않다면
- 헤드의 prev 프로퍼티가 새로운 노드가 되도록하고
- 새로운 노드의 next 프로퍼티가 현재 헤드가 되도록 한다
- 마지막으로 헤드 표시를 옮겨서 새로운 노드가 헤드가 되도록 한다

Unshift 메소드 솔루션

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;
	}
	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 메소드

Get

get은 숫자인 인덱스를 입력하게 되어있다. 그 인덱스 위치에 있는 노드를 출력한다. 단일 연결 리스트에서 했던대로 코딩할 수 있습니다. 그렇지만 아주 작은 최적화가 추가되죠. 이건 이중 연결 리스트에서만 할 수 있는 꽤 큰 변화다.

의사코드

인덱스가 유효한지 확인한다. 음수이거나 길이와 같거나 크다면 null을 출력한다
만약 인덱스가 리스트의 길이의 절반보다 작거나 같다면
- 목록 전체를 헤드부터 시작하여 중간까지 돌립니다.
- 찾은 노드 하나를 반환합니다.
만약 인덱스가 리스트의 길이의 절반보다 크다면
- 목록 전체를 테일부터 시작하여 중간까지 돌립니다.
- 찾은 노드 하나를 반환합니다.

Get 메소드 솔루션

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;
	}
	get(index){
		if(index < 0 || index >= this.length) return undefined;
		var count, current;
		if(index <= this.length/2){
			count = 0;
			current = this.head;
			while (count! = index) {
				currnt = current.next;
				count++;
			}
		} else {
			count = this.length - 1;
			current = this.tail;
			while (count! = index) {
				currnt = current.next;
				count--;
			}
		}
		return current;
	}
}

Set 메소드

Set

더블 연결 리스트의 노드의 값을 대체한다

의사코드

함수에 입력된 인덱스 값을 넣은 get 메소드의 결곽밧을 받는 변수를 만들어 줍니다.
- get이 인덱스가 음수이거나 길이보다 크거나 같은지는 확인해 줄거다.
- get에서 유효한 값이 출력되면 해당 노드의 값을 우리가 입력한 값으로 바꿔준 다음에 참을 출력한다.
그렇지 않다면 false 출력한다.

Set 메소드 솔루션

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;
	}
	get(index){
		if(index < 0 || index >= this.length) return undefined;
		var count, current;
		if(index <= this.length/2){
			count = 0;
			current = this.head;
			while (count! = index) {
				currnt = current.next;
				count++;
			}
		} else {
			count = this.length - 1;
			current = this.tail;
			while (count! = index) {
				currnt = current.next;
				count--;
			}
		}
		return current;
	}
		set(index, val){
			var foundNode = this.get(index);
			if(foundNode != null){
				foundNode.val = val;
				return true;
			}
			return false;
		}
}

Insert 메소드

Insert

특정 위치의 이중 연결 리시트에 노드를 추가한다. 노드를 찾으면 연결을 모두 없애줘야한듯

의사코드

인덱스가 유효한지 검사한다. 인덱스가 임수거나 길이보다 크거나 같으면 false를 반환한다.
만약 인덱스가 0이면, unshift
만약 인덱스가 길이와 같다면, push
그렇지 않다면 get 메소드를 사용해서 우리가 삽입하려고 하는 바로 전에 오는 값에 접근해야 합니다.
next, prev 프로퍼티를 사용해서 노드를 연결해준다.
길이를 증가시킨다.
true 를 반환한다.

Insert 메소드 솔루션

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){
		if(this.length === 0){
			this.head = newNode;
			this.tail = newNode;
		} else{
			this.tail.next = newNode;
			nesNode.prev= this.tail;
			this.tail = newNode;
		}
		this.length++;
		return this;
	}
	get(index){
		if(index < 0 || index >= this.length) return undefined;
		var count, current;
		if(index <= this.length/2){
			count = 0;
			current = this.head;
			while (count! = index) {
				currnt = current.next;
				count++;
			}
		} else {
			count = this.length - 1;
			current = this.tail;
			while (count! = index) {
				currnt = current.next;
				count--;
			}
		}
		return current;
	}
	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;
	}
	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 foundNode = 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 메소드

Remove

특정 위치의 이중 연결 리스트의 노드를 제거한다.

의사코드

인덱스가 유효헌지 검사. 0보다 작거나, length보다 같거나 크면 undefined를 반환한다.
인덱스가 0이면, shift
인덱스가 길이 - 1과 같다면, pop
위의 것이 다 아닌 경우 get 메소드를 사용해서 제거해야하는 요소를 찾는다.
next와 prev 프로퍼티를 바꿔서 제대로 제거해 줍니다.
찾아낸 next와 prev를 없애서 출력할 준비를 해준다. 그냥 값만 남기고 next와 prev 값을 null로 설정
길이에서 1을 빼고
제거된 노드를 출력한다.

Remove 메소드 솔루션

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;
	}
	get(index){
		if(index < 0 || index >= this.length) return undefined;
		var count, current;
		if(index <= this.length/2){
			count = 0;
			current = this.head;
			while (count! = index) {
				currnt = current.next;
				count++;
			}
		} else {
			count = this.length - 1;
			current = this.tail;
			while (count! = index) {
				currnt = current.next;
				count--;
			}
		}
		return current;
	}
	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;
		}
		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;
		}
			this.head = oldHead.next;
			this.head.prev= null;
			oldHead.next = null;
			this.length--;
			return oldHead;
	}
	remove(index) {
			if(index < 0 || index > this.length) return false;
			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;
			removed.next = null;
			removed.prev = null;
			this.length--;
			return removedNode;
	}
}

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

정확하게 searching은 O(n /2) 지만 O(n)이라고 한다.

<aside> 💡 요약

이중 연결 리스트는 그 전에 있는 노드를 가리키는 포이터가 하나 더 있다는 점만 빼면 단일 연결 리스트와 똑같다.
이중 연결 리스트는 무언가 찾는데 더 나은 성능을 발휘한다. 왜냐하면 절반의 시간이 걸리니까요.
그러나 추가로 만든 포인터는 메모리를 더 소모하므로 약점이 되기도 합니다. </aside>

이중 연결 리스트는 브라우저의 뒤로가기와 앞으로 가기와 같다

저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘👽] 16. 이진 검색 트리 (0)	2022.09.20
[알고리즘👽] 15. 스택과 큐 (0)	2022.09.19
[알고리즘👽] 13. 단일 연결 리스트(2) (0)	2022.09.17
[알고리즘👽] 13. 단일 연결 리스트(1) (0)	2022.09.17
[알고리즘👽] 12. 자료구조 (0)	2022.09.15

현재글[알고리즘👽] 14. 이중 연결 리스트

개발

프론트엔드 중심으로 공부한 내용 정리해서 업로드합니다.

알고리즘 큐, js유효성검사, git push -u option, 회고록, git push -u origin main 뜻, 알고리즘, git 초기화, Tailwind단점, http 캐시, 프론트엔드 면접질문, git과 github차이, 알고리즘 스택, gitlab github 차이, OpenSlide, git push -u 옵션, REACT, git init 초기화, Tailwind장점, JavaScript, javascirpt,

Today :
Yesterday :

« 2025/02 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28