이 글에서는 배열과 연결리스트에 대해서 알아보겠다.
배열과 연결리스트는 모두 선형 자료구조로 비슷하면서도 반대의 특성을 가지고 있다.
배열은 데이터를 물리적 주소에 순차적으로 저장하며 인덱스를 가지고 있어 바로 접근할 수 있기 때문에 접근 속도가 매우 빠르다. 그러나, 배열은 크가가 고정되어 있기 때문에 처음 지정된 사이즈보다 더 많은 데이터를 넣으려면 배열의 크기를 늘리는 연산을 해야하고 데이터 삽입/삭제시 해당 위치 다음칸에 있는 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야하기 때문에 데이터 삽입/삭제에는 약한 모습을 보인다.
연결리스트는 데이터를 저장할 때 데이터만 저장하는 것이 아니라 다음 데이터의 물리적 주소까지 같이 저장한다. (단순 연결리스트는 다음 데이터의 주소를, 이중 연결리스트는 이전 주소와 다음 주소를 모두 저장)
특정 데이터에 접근할 때 인덱스로 바로 접근할 수 있었던 배열과 달리 첫 노드부터 원하는 노드까지 링크를 따라가야 접근이 가능하기 때문에 배열에 비해 접근 속도는 떨어진다.
하지만 반대로, 데이터를 삽입/삭제 할 때에는 물리적 주소에 구애받지 않고 앞/뒤 노드의 주소만 끼워넣을 노드의 주소로 바꿔주면 되기 때문에 삽입/삭제는 배열보다 빠르다.
자바스크립트로 구현한 양방향 연결리스트(Double Linked List)
/**
* 연결리스트(LinkedList)에서 사용할 노드 클래스
*/
class Node {
constructor(_prev, _data, _next) {
this.prev = _prev;
this.data = _data;
this.next = _next;
}
}
/**
* LinkedList 자료구조 클래스
*/
class LinkedList {
constructor() {
let head = null;
let tail = null;
let size = 0;
/**
* 해당 인덱스의 노드를 반환
*/
const node = (index) => {
if (index < size / 2 ) {
// 인덱스가 사이즈의 절반보다 작으면 앞(head)에서부터부터 탐색
let cursor = head;
for (let i = 0; i < index; i++) {
cursor = cursor.next;
}
return cursor;
} else {
// 인덱스가 사이즈의 절반보다 크면 뒤(tail)에서부터 탐색
let cursor = tail;
for (let i = size -1; i > index; i--) {
cursor = cursor.prev;
}
return cursor;
}
};
/**
* 리스트의 맨 앞에 노드를 추가
* @param data
*/
this.addFirst = (data) => {
const newNode = new Node(null, data, head);
if (head !== null) {
head.prev = newNode;
}
head = newNode;
size ++;
if (head.next === null) {
tail = newNode;
}
};
/**
* 리스트의 맨 뒤에 노드를 추가
* @param data
*/
this.addLast = (data) => {
const newNode = new Node(tail, data, null);
if (tail !== null) {
tail.next = newNode;
}
tail = newNode;
size ++;
if (tail.prev === null) {
head = newNode;
}
};
/**
* 인덱스를 지정해 노드를 추가
* @param k
* @param data
*/
this.add = (k, data) => {
const prev = node(k-1);
if (prev === null) {
this.addFirst(data);
} else {
const next = prev.next;
const newNode = new Node(prev, data, next);
prev.next = newNode;
if (next !== null) {
next.prev = newNode;
}
size ++;
if (next === null) {
tail = newNode;
}
}
};
/**
* 리스트의 맨 앞 노드를 삭제
*/
this.removeFirst = () => {
if (head) {
let temp = head;
head = temp.next;
if (head === null) {
tail = null;
} else {
head.prev = null;
}
temp = null;
size--;
}
};
/**
* 리스트의 맨 뒤 노드를 삭제
*/
this.removeLast = () => {
if (tail) {
let temp = tail;
tail = temp.prev;
if (tail === null) {
head = null;
} else {
tail.next = null;
}
temp = null;
size --;
}
};
/**
* 인덱스를 지정해 노드를 삭제
* @param index
*/
this.remove = (index) => {
let target = node(index);
if (target) {
const prev = target.prev;
const next = target.next;
if (prev === null) {
return this.removeFirst();
}
if (next === null) {
return this.removeLast();
}
prev.next = target.next;
next.prev = target.prev;
target = null;
size --;
}
};
/**
* Head를 반환
*/
this.getHead = () => head;
/**
* Tail을 반환
*/
this.getTail = () => tail;
/**
* 해당 인덱스의 노드를 반환
* @param k
*/
this.get = (k) => node(k);
/**
* 리스트의 크기를 반환
*/
this.size = () => size;
}
}
const linkedList = new LinkedList();
//-----삽입-----
linkedList.addFirst('사과'); // 사과
linkedList.addFirst('귤'); // 귤-사과
linkedList.addLast('바나나'); // 귤-사과-바나나
linkedList.addLast('오렌지'); // 귤-사과-바나나-오렌지
linkedList.add(2, '레몬'); // 귤-사과-레몬-바나나-오렌지
//-----삭제-----
linkedList.removeFirst(); // 사과-레몬-바나나-오렌지
linkedList.removeLast(); // 사과-레몬-바나나
linkedList.remove(0); // 사과-바나나
//-----리스트 출력-----
const result = [];
let cursor = linkedList.getHead();
while(cursor) {
result.push(cursor.data);
cursor = cursor.next;
}
console.log(result);