IMMERSIVE
Linked List
연결 리스트(링크드 리스트)는 각 노드가 다른 노드를 가리키는 자료 구조이다. 고정된 크기를 갖는 배열과 달리 연결 리스트는 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료구조이다. 즉, 처음부터 크기를 정해놓는 것이 아닌 사용하면서 크기를 늘리거나 줄일 수 있다는 것이다. 링크드 리스트는 크게 단일(single) 링크드 리스트와 이중(double) 링크드 리스크가 있다.
링크드 리스트의 맨 앞 노드(시작부분)를 Head,맨 마지막 노드(끝 부분)을 Tail이라고 한다. 아무 값도 없을 경우 null이 기본값이 된다.
1. 단일 링크드 리스트
1.1 초기화
단일 링크드 리스트는 각 노드가 다음 노드에 대한 참조를 갖는 구조이다. 여기서 노드는 데이터 한 단위를 의미한다. 각 노드는 value와 next 속성을 갖는다. value는 링크드 리스트 각 노드의 값을 저장하고, next는 다음 나도에 대한 포인터(다른 노드를 가리키는 역할) 역할을 한다.
시작 부분을 Head라고 하고, 어떤 항목도 삽입되기 전에 Head의 속성은 null이다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SlnglyLiskedList {
constructor() {
this.head = null;
this.size = 0;
}
inEmpty() {
return this.size === 0;
}
}
1.2 삽입
Head가 비어있는 경우 신규노드로 설정한다. 비어있지 않다면 temp라는 변수를 만들어 이전 헤드를 잠시 저장해놓고, 새로운 Head를 신규로 추가한다. 마지막으로 새로운 Head의 next는 temp를 기리키도록 지정한다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SlnglyLiskedList {
constructor() {
this.head = null;
this.size = 0;
}
inEmpty() {
return this.size === 0;
}
// 삽입
insert(value) {
if (this.head === null) {
this.head = new Node(value);
} else {
let temp = this.head;
this.head = new Node(value);
this.head.next = temp;
}
this.size += 1;
}
}
1.3 삭제
단일 링크드 리스트에서 노드를 삭제하는 것은 해당 노도의 참조를 제거함으로써 구현할 수 있다. 삭제하고자 하는 노드가 링크드 리스트의 중간에 있다면 삭제하고자 하는 노드의 next 포인터가 가리키는 노드를 찾는다. 그리고 삭제하고자 하는 노드의 이전 노드의 next 포인터가 삭제하고자 하는 노드의 다음 노드를 가리키도록 한다.
삭제히고자 하는 노드가 단일 링크드 리스트 끝에 위치한다면 마지막에서 두번 째 노드가 자신의 속성을 null로 설정해 해당 노드의 참조를 끊으면 된다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SlnglyLiskedList {
constructor() {
this.head = null;
this.size = 0;
}
inEmpty() {
return this.size === 0;
}
// 삽입
insert(value) {
if (this.head === null) {
this.head = new Node(value);
} else {
let temp = this.head;
this.head = new Node(value);
this.head.next = temp;
}
this.size += 1;
}
// 삭제
remove(value) {
let currentHead = this.head;
if (currentHead.value === value) {
this.head = currentHead.next;
this.size -= 1;
} else {
let prevNode = currentHead;
while(currentHead.next) {
if (currentHead.value === value) {
prevNode.next = currentHead.next;
prevNode = currentHead;
currentHead = currentHead.next;
break;
}
prevNode = currentHead;
currentHead = currentHead.next;
}
if (currentHead.value === value) {
prevNode.next = null;
}
this.size -= 1;
}
}
}
1.4 헤드 항목 삭제
링크드 리스트 헤드에 있는 항목을 삭제하는 것도 가능하다. 노드가 헤드에서 삭제될 때 순회가 필요 없이, 맨 앞에 있는 요소를 삭제하면 된다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SlnglyLiskedList {
constructor() {
this.head = null;
this.size = 0;
}
inEmpty() {
return this.size === 0;
}
// 삽입
insert(value) {
if (this.head === null) {
this.head = new Node(value);
} else {
let temp = this.head;
this.head = new Node(value);
this.head.next = temp;
}
this.size += 1;
}
// 삭제
remove(value) {
let currentHead = this.head;
if (currentHead.value === value) {
this.head = currentHead.next;
this.size -= 1;
} else {
let prevNode = currentHead;
while(currentHead.next) {
if (currentHead.value === value) {
prevNode.next = currentHead.next;
prevNode = currentHead;
currentHead = currentHead.next;
break;
}
prevNode = currentHead;
currentHead = currentHead.next;
}
if (currentHead.value === value) {
prevNode.next = null;
}
this.size -= 1;
}
}
// 헤드 삭제
deleteHead() {
let currentHead = null;
if (this.head !== null) {
result = this.head.value;
this.head = this.head.next;
this.size -= 1;
}
return currentHead;
}
}
1.5 검색
어떤 값이 링크드 리스트에 존재하는지 확인하기 위해선 next 포인터를 반복해서 확인해야 한다. 삭제와 마찬가지로 최악의 경우 전체 링크드 리스트를 살펴봐야 한다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SlnglyLiskedList {
constructor() {
this.head = null;
this.size = 0;
}
inEmpty() {
return this.size === 0;
}
// 삽입
insert(value) {
if (this.head === null) {
this.head = new Node(value);
} else {
let temp = this.head;
this.head = new Node(value);
this.head.next = temp;
}
this.size += 1;
}
// 삭제
remove(value) {
let currentHead = this.head;
if (currentHead.value === value) {
this.head = currentHead.next;
this.size -= 1;
} else {
let prevNode = currentHead;
while(currentHead.next) {
if (currentHead.value === value) {
prevNode.next = currentHead.next;
prevNode = currentHead;
currentHead = currentHead.next;
break;
}
prevNode = currentHead;
currentHead = currentHead.next;
}
if (currentHead.value === value) {
prevNode.next = null;
}
this.size -= 1;
}
}
// 헤드 삭제
deleteHead() {
let currentHead = null;
if (this.head !== null) {
result = this.head.value;
this.head = this.head.next;
this.size -= 1;
}
return currentHead;
}
// 검색
find(value) {
let currentHead = this.head;
while(currentHead.next) {
if (currentHead.value === value) {
return true;
}
currentHead = currentHead.next;
}
return false;
}
}
2. 이중 링크드 리스트
이중 링크드 리스트를 양방향 단일 링크드 리스트라고 생각해야 된다. 이중 링크드 리트의 각 노드에는 next, prev 포인터가 있다.
역시 헤드는 시작, 테일은 끝을 의미한다. 이중 링크드 리스트에서도 삽입, 삭제, 검색을 모두 구현할 수 있으며, 단일 링크드 리스트와 방식도 비슷하다. 삽입과 삭제의 경우 next, prev속성 모두를 갱신해야 한다.
2.1 초기화
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
}
2.2 헤드에 노드 삽입
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
// 헤드 삽입
addAtHead(value) {
if (this.head === null) {
this.head = new Node(value);
this.tail = this.head;
} else {
const temp = new Node(value);
temp.next = this.head;
this.head.prev = temp;
this.head = temp;
}
this.size += 1;
}
}
2.3 테일에 노드 삽입
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
// 헤드 삽입
addAtHead(value) {
if (this.head === null) {
this.head = new Node(value);
this.tail = this.head;
} else {
const temp = new Node(value);
temp.next = this.head;
this.head.prev = tmep;
this.head = temp;
}
this.size += 1;
}
// 테일 삽입
addAtTail(value) {
if (this.tail === null) {
this.tail = new Node(value);
this.head = this.tail;
} else {
const temp = new Node(value);
temp.prev = this.tail;
this.tail.next = temp;
this.tail = temp;
}
this.size += 1;
}
}
2.4 헤드 항목 삭제
항목이 하나만 존재하면, 헤드와 테일이 동일하다. 그럴 경우 헤드, 테일 모두 null로 설정한다. 항목이 여러개 존재하는 경우 헤드를 헤드의 next포인터로 설정한다. 마지막으로 새로운 헤드의 prev를 null로 설정해 예전 헤드에 대한 참조를 제거한다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
// 헤드 삽입
addAtHead(value) {
if (this.head === null) {
this.head = new Node(value);
this.tail = this.head;
} else {
const temp = new Node(value);
temp.next = this.head;
this.head.prev = tmep;
this.head = temp;
}
this.size += 1;
}
// 테일 삽입
addAtTail(value) {
if (this.tail === null) {
this.tail = new Node(value);
this.head = this.tail;
} else {
const temp = new Node(value);
temp.prev = this.tail;
this.tail.next = temp;
this.tail = temp;
}
this.size += 1;
}
// 헤드 삭제
deleteHead() {
let currentHead = null;
if (this.head !== null) {
currentHead = this.head.value;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
}
this.size -= 1;
return currentHead;
}
// 테일 삭제
deleteTail() {
let currentTail = null;
if (this.tail !== null) {
currentTail = this.tail.value;
if (this.tail === this.head) {
this.tail = null;
this.head = null;
} else {
this.tail = this.tail.prev;
this.tail.next= null;
}
}
this.size -= 1;
return currentTail;
}
}
2.5 검색
어떠한 값이 이중 링크드 리스트에 존재하는지 확인하기 위해서 Head => Tail or Tail => Head 방향으로 검색을 할 수 있다. 헤드에서 시작하는 경우 헤드의 next포인터를 사용하면 된다. 반대로 테일에서 시직할 경우 테일의 prev포인터를 사용하면 된다. 마찬가지로 최악의 경우 전체 리스트를 모두 확인해야하는 경우가 있을 수 있다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
// 헤드 삽입
addAtHead(value) {
if (this.head === null) {
this.head = new Node(value);
this.tail = this.head;
} else {
const temp = new Node(value);
temp.next = this.head;
this.head.prev = tmep;
this.head = temp;
}
this.size += 1;
}
// 테일 삽입
addAtTail(value) {
if (this.tail === null) {
this.tail = new Node(value);
this.head = this.tail;
} else {
const temp = new Node(value);
temp.prev = this.tail;
this.tail.next = temp;
this.tail = temp;
}
this.size += 1;
}
// 헤드 삭제
deleteHead() {
let currentHead = null;
if (this.head !== null) {
currentHead = this.head.value;
if (this.tail === this.head) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
}
this.size -= 1;
return currentHead;
}
// 테일 삭제
deleteTail() {
let currentTail = null;
if (this.tail !== null) {
currentTail = this.tail.value;
if (this.tail === this.head) {
this.tail = null;
this.head = null;
} else {
this.tail = this.tail.prev;
this.tail.next= null;
}
}
this.size -= 1;
return currentTail;
}
findHeadToTail(value) {
let currentHead = this.head;
while(currentHead) {
if (currentHead.value === value) {
return true;
}
currentHead = currentHead.next;
}
return false;
}
findTailToHead(value) {
let currentTail = this.head;
while(currentTail) {
if (currentTail.value === value) {
return true;
}
currentTail = currentTail.prev;
}
return false;
}
}
정리
링크드 리스트는 다른 노드에 대한 next 포인터, prev 포인터를 지닌 각 노드에 의해 동작한다. 단일 링크드 리스트와 이중 링크트 리스드 모두 삽입 시간은 *O(1)*의 상수 시간 복잡도를 가진다. 헤드와 테일에서 노드를 삭제하는 경우도 *O(1)*의 상수 시간 복잡도를 가진다. 하지만 검색은 단일, 이중 모두 *O(n)*의 시간 복잡도를 가진다. 양방향 검색을 하려면 이중 링크드 리스트를 만들어야 한다. 단일 링크드 리스트의 경우 헤드로부터 항목을 빠르게 얻을 수 있지만, 테일로 부터 값을 얻으려면 오랜 시간이 걸린다는 단점이 있다. 따라서 이중 링크드 리스트를 사용하면 좀 더 유연하고 빠르다는 장점이 있다.