연결 리스트
- 연결 리스트는 일련의 원소를 배열처럼 순차적으로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는 자료구조이다. 즉, 논리적인 순서는 지켜지지만 물리적인 순서는 상관하지 않는다.
- data와 address 정보를 가지는 노드들이 연결된 형태이며 address에는 다음 연결된 노드의 주소가 담겨있다.
- 연결 리스트의 종류에는 구현 방법에 따라 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다.
※ 시간복잡도 비교
- 연결 리스트는 데이터의 삽입 및 삭제의 경우 배열 보다 유리하다.
- 배열에서의 데이터 공간을 늘리거나 줄이지 않아도 되기 때문이다.
- 연결 리스트는 데이터의 탐색의 경우는 배열 보다 불리하다.
- 배열은 인덱스를 통한 임의접근이 가능하지만 연결 리스트의 경우 특정 원소를 처음부터 찾아야 하기 때문이다.
- 위의 경우는 탐색과, 삽입 및 삭제의 경우에만 해당하는 시간복잡도이며 전체적인 구현에서의 시간 복잡도는 상황마다 상이하므로 아래의 구현 코드를 보며 이해해보자.
1. 단순 연결 리스트
구현 - javaScript
'use strict';
class Node {
constructor(value) {
this.data = value;
this.link = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
find(idx) {
let curNode = this.head;
let count = 0;
while (count !== idx) {
curNode = curNode.link;
count++;
}
if (!curNode) {
console.log('해당 위치의 데이터가 존재 하지 않습니다.\n');
return;
}
return curNode;
}
append(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.link = newNode;
this.tail = newNode;
}
this.length++;
return;
}
removeLast() {
const removeNode = this.tail;
if (this.isEmpty()) {
console.log('이미 데이터가 존재 하지 않습니다.');
return;
}
if (this.length === 1) {
this.head = null;
this.tail = null;
this.length--;
return removeNode.data;
}
let curNode = this.head;
while (curNode.link !== this.tail) {
curNode = curNode.link;
}
curNode.link = null;
this.tail = curNode;
this.length--;
return removeNode.data;
}
prepend(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
const temp = this.head;
this.head = newNode;
this.head.link = temp;
}
this.length++;
return;
}
removeFirst() {
const removeNode = this.head;
if (this.isEmpty()) {
console.log('이미 데이터가 존재하지 않습니다.');
return;
}
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = removeNode.link;
}
this.length--;
return removeNode;
}
insert(idx, value) {
if (idx >= this.length) {
console.log(
'리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
);
return this.append(value);
} else if (idx === 0) {
return this.prepend(value);
}
const newNode = new Node(value);
const prevNode = this.find(idx - 1);
newNode.link = prevNode.link;
prevNode.link = newNode;
this.length++;
return;
}
remove(idx) {
if (idx >= this.length) {
console.log('리스트에 존재하지 않는 인덱스입니다.');
return;
} else if (idx === 0) {
return this.removeFirst();
} else if (idx === this.length - 1) {
return this.removeLast();
}
const prevNode = this.find(idx - 1);
const removeNode = prevNode.link;
prevNode.link = removeNode.link;
this.length--;
return removeNode;
}
isEmpty() {
return this.length === 0 ? true : false;
}
printList() {
let cur = this.head;
let str = '';
while (cur) {
str += cur.data + ' ';
cur = cur.link;
}
if (str.length === 0) {
console.log('데이터가 존재하지 않습니다.\n');
} else {
console.log(`List Size : ${this.size()} \n${str} \n`);
}
return;
}
size() {
return this.length;
}
}
const singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.append(1);
singlyLinkedList.printList();
singlyLinkedList.append(2);
singlyLinkedList.printList();
singlyLinkedList.removeLast();
singlyLinkedList.printList();
singlyLinkedList.removeLast();
singlyLinkedList.printList();
singlyLinkedList.prepend(1);
singlyLinkedList.printList();
singlyLinkedList.prepend(2);
singlyLinkedList.printList();
singlyLinkedList.removeFirst();
singlyLinkedList.printList();
singlyLinkedList.insert(1, 2);
singlyLinkedList.printList();
singlyLinkedList.insert(1, 3);
singlyLinkedList.printList();
singlyLinkedList.remove(1);
singlyLinkedList.printList();
- 결과
2. 이중 연결 리스트
- 단순 연결 리스트는 한 방향으로만 연결되어 있어 특정 노드의 전 노드를 알려면 전체 탐색이 필요하다.
- 위와 같은 경우를 보완하여 양쪽 방향 모두의 노드를 연결한 리스트가 이중 연결 리스트이다.
- 이전 노드의 주소, 데이터, 다음 노드의 주소를 가지므로 단일 연결리스트에 비해 메모리를 2배 만큼 더 사용하게 된다.
- 이중 연결 리스트의 경우 removeLast() 메소드의 시간 복잡도가 단일 연결 리스트에서의 O(n)에서 O(1)으로 개선되었다. 아래의 코드를 자세히 살펴보자.
구현 - javaScript
'use strict';
class Node {
constructor(value) {
this.data = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
find(idx) {
let curNode = this.head;
let count = 0;
while (count !== idx) {
curNode = curNode.next;
count++;
}
if (!curNode) {
console.log('해당 위치에 데이터가 존재하지 않습니다.');
return;
}
return curNode;
}
append(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
return;
}
removeLast() {
const removeNode = this.tail;
if (this.isEmpty()) {
console.log('이미 데이터가 존재하지 않습니다.\n');
return;
}
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.length--;
return removeNode;
}
prepend(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return;
}
removeFirst() {
const removeNode = this.head;
if (this.isEmpty()) {
console.log('이미 데이터가 존재하지 않습니다.\n');
return;
}
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.length--;
return removeNode;
}
insert(idx, value) {
if (idx >= this.length) {
console.log(
'리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
);
return this.append(value);
} else if (idx === 0) {
return this.prepend(value);
}
const newNode = new Node(value);
const prevNode = this.find(idx - 1);
prevNode.next.prev = newNode;
newNode.next = prevNode.next;
prevNode.next = newNode;
newNode.prev = prevNode;
this.length++;
return;
}
remove(idx) {
if (idx >= this.length) {
console.log('리스트에 존재하지 않는 인덱스입니다.');
return;
} else if (idx === 0) {
return this.removeFirst();
} else if (idx === this.length - 1) {
return this.removeLast();
}
const removeNode = this.find(idx);
const prevNode = removeNode.prev;
prevNode.next = removeNode.next;
removeNode.next.prev = prevNode;
this.length--;
return removeNode;
}
isEmpty() {
return this.length === 0 ? true : false;
}
printList() {
let curNode = this.head;
let str = '';
while (curNode) {
str += curNode.data + ' ';
curNode = curNode.next;
}
if (str.length === 0) {
console.log('데이터가 존재하지 않습니다.\n');
} else {
console.log(`List Size : ${this.size()} \n${str} \n`);
}
return;
}
size() {
return this.length;
}
}
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.append(1);
doublyLinkedList.printList();
doublyLinkedList.append(2);
doublyLinkedList.printList();
doublyLinkedList.removeLast();
doublyLinkedList.printList();
doublyLinkedList.removeLast();
doublyLinkedList.printList();
doublyLinkedList.prepend(1);
doublyLinkedList.printList();
doublyLinkedList.prepend(2);
doublyLinkedList.printList();
doublyLinkedList.removeFirst();
doublyLinkedList.printList();
doublyLinkedList.insert(1, 2);
doublyLinkedList.printList();
doublyLinkedList.insert(1, 3);
doublyLinkedList.printList();
doublyLinkedList.remove(1);
doublyLinkedList.printList();
console.log(doublyLinkedList);
- 결과
3. 원형 연결 리스트
- 단순 연결 리스트나 이중 연결 리스트에서 tail이 head로 연결되는 연결리스트이다.
'use strict';
class Node {
constructor(value) {
this.data = value;
this.prev = null;
this.next = null;
}
}
class CircularLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
find(idx) {
let curNode = this.head;
let count = 0;
while (count !== idx) {
if(curNode.next === this.head) break;
curNode = curNode.next;
count++;
}
if (!curNode) {
console.log('해당 위치에 데이터가 존재하지 않습니다.');
return;
}
return curNode;
}
append(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
newNode.next = this.head;
this.head.prev = newNode;
this.tail = newNode;
}
this.length++;
return;
}
removeLast() {
const removeNode = this.tail;
if (this.isEmpty()) {
console.log('이미 데이터가 존재하지 않습니다.\n');
return;
}
if (this.size() === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = this.head;
}
this.length--;
return removeNode;
}
prepend(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.head.prev = this.tail;
this.tail.next = this.head;
}
this.length++;
return;
}
removeFirst() {
const removeNode = this.head;
if (this.isEmpty()) {
console.log('이미 데이터가 존재하지 않습니다.\n');
return;
}
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = removeNode.next;
this.head.prev = this.tail;
this.tail.next = this.head;
}
this.length--;
return removeNode;
}
insert(idx, value) {
if (idx >= this.length) {
console.log(
'리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
);
return this.append(value);
} else if (idx === 0) {
return this.prepend(value);
}
const newNode = new Node(value);
const prevNode = this.find(idx - 1);
prevNode.next.prev = newNode;
newNode.next = prevNode.next;
prevNode.next = newNode;
newNode.prev = prevNode;
this.length++;
return;
}
remove(idx) {
if (idx >= this.length) {
console.log('리스트에 존재하지 않는 인덱스입니다.');
return;
} else if (idx === 0) {
return this.removeFirst();
} else if (idx === this.length - 1) {
return this.removeLast();
}
const removeNode = this.find(idx);
const prevNode = removeNode.prev;
prevNode.next = removeNode.next;
removeNode.next.prev = prevNode;
this.length--;
return removeNode;
}
isEmpty() {
return this.length === 0 ? true : false;
}
printList() {
let curNode = this.head;
let str = '';
while (curNode) {
str += curNode.data + ' ';
curNode = curNode.next;
if(curNode === this.head) break;
}
if (str.length === 0) {
console.log('데이터가 존재하지 않습니다.\n');
} else {
console.log(`List Size : ${this.size()} \n${str} \n`);
}
return;
}
size() {
return this.length;
}
}
const circularLinkedList = new CircularLinkedList();
circularLinkedList.append(1);
circularLinkedList.printList();
circularLinkedList.append(2);
circularLinkedList.printList();
circularLinkedList.append(3);
circularLinkedList.printList();
circularLinkedList.removeLast();
circularLinkedList.printList();
circularLinkedList.removeLast();
circularLinkedList.printList();
circularLinkedList.removeLast();
circularLinkedList.printList();
circularLinkedList.prepend(1);
circularLinkedList.printList();
circularLinkedList.prepend(2);
circularLinkedList.printList();
circularLinkedList.prepend(3);
circularLinkedList.printList();
circularLinkedList.removeFirst();
circularLinkedList.printList();
circularLinkedList.removeFirst();
circularLinkedList.printList();
circularLinkedList.insert(1, 2);
circularLinkedList.printList();
circularLinkedList.insert(1, 3);
circularLinkedList.printList();
circularLinkedList.remove(1);
circularLinkedList.printList();
console.log(circularLinkedList);