연결리스트(Linked List)란?
데이터를 순서대로 나열한 자료구조로 순서가 있는 데이터를 관리할 때 사용한다.
배열(배열 문서 참고)과 유사하지만, 배열과는 달리 데이터가 메모리상에 연속적으로 위치하지는 않는다.
각 데이터는 포인터로 연결되어 있어 데이터끼리 물리적으로 떨어져 있어도 된다.
HEAD포인터, 리스트요소들로 구성되어있다.
HEAD포인터는 첫번째 리스트요소의 위치정보를 저장한다.
그래서 리스트의 데이터 유무는 HEAD포인터만 확인하는것으로 쉽게 알 수 있다.
각 리스트 요소는 NEXT포인터를 가지고 있다.
각 리스트의 요소는 다음 요소의 위치정보를 가지고 있는 NEXT포인터를 가지고있다.
마지막 요소는 NEXT포인터가 없는 것으로 구별한다.
연결리스트의 장점
데이터의 삽입/삭제 성능이 빠르다.
데이터의 삽입/삭제 후 다른 요소들의 위치를 변경시킬 필요 없이 데이터의 포인터들만 변경시켜주면 된다. - O(1) 실행시간
연결리스트의 단점
순차 접근(sequential access)만 가능하므로 검색이 비효율적이다.
연결리스트에서 조회를 하려면 리스트의 첫 요소(head)부터 순차적으로 조회를 해야하므로 검색 성능이 좋지 않다.- O(n) 실행시간
모든 요소의 값을 다 읽어야 한다면 괜찮지만, 특정한 요소를 조회할때는 그 전의 모든 요소들을 조회해야하므로 비효율적이다.
따라서 조회 연산이 많은 상황이라면 연결리스트보다는 배열이 더 적절한 자료구조이다.
인터페이스
- head - 리스트의 첫 요소
- length - 리스트의 길이
- append(element) - 리스트의 끝에 요소를 추가한다
- insert(position, element) - 특정 위치에 요소를 추가한다.
- remove(element) - 특정 요소를 삭제한다.
- removeAt(position) - 특정 위치의 요소를 삭제한다.
- indexOf(element) - 요소의 인덱스를 반환한다.
- isEmpty() - 리스트가 비었는지 확인한다.
- size() - 요소의 갯수를 반환한다.
- toString() - 전체 리스트요소를 문자열로 반환한다.
구현 - JavaScript에서의 연결리스트
class LinkedListNode {
constructor(element) {
this._element = element;
this._next = null;
}
get element() {
return this._element;
}
get next() {
return this._next;
}
set next(node) {
this._next = node;
}
toString() {
return `element: ${this.element} / next: ${this.next && this.next.element}`;
}
}
class LinkedList {
constructor() {
this._head = null;
this._length = 0;
}
get head() {
return this._head;
}
set head(node) {
this._head = node;
}
get length() {
return this._length;
}
set length(val) {
this._length = val;
}
append(element) {
const node = new LinkedListNode(element);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
let last = current;
last.next = node;
}
this.length++;
}
insert(position, element) {
if (
typeof position !== "number" ||
position < 0 ||
position > this.length - 1
) {
return false;
}
const node = new LinkedListNode(element);
if (position === 0) {
node.next = this.head;
this.head = node;
} else {
const previous = this._findPreviousByPosition(position);
node.next = previous.next;
previous.next = node;
}
this.length++;
}
remove(element) {
if (!this.head) {
return null;
}
if (this.head.element === element) {
this.head = this.head.next;
} else {
let current = this.head;
let previous;
while (current && !previous) {
if (current.next && current.next.element === element) {
previous = current;
}
current = current.next;
}
const target = previous.next;
previous.next = target.next;
}
this.length--;
}
removeAt(position) {
if (
typeof position !== "number" ||
position < 0 ||
position > this.length - 1
) {
return false;
}
if (position === 0) {
this.head = this.head.next;
} else {
const previous = this._findPreviousByPosition(position);
const target = previous.next;
previous.next = target.next;
}
this.length--;
}
indexOf(element) {
let current = this.head;
let index = 0;
while (current) {
if (current.element === element) {
return index;
}
current = current.next;
index++;
}
return -1;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
toString() {
let result = "### Linked List ###\n\n";
result += `[head] ${this.head.toString()}\n\n`;
let current = this.head;
while (current) {
result += `[node] ${current.toString()}\n`;
current = current.next;
}
result += `\nlength: ${this.length}`;
return result;
}
_findPreviousByPosition(position) {
let previous = this.head;
let loopTime = 0;
while (loopTime++ < position - 1) {
previous = previous.next;
}
return previous;
}
}
// Test
it("LinkedList 클래스는 잘 동작한다.", () => {
const linkedList = new LinkedList();
linkedList.append("쿠스");
linkedList.append("톰");
linkedList.append("마이클");
linkedList.append("미셀");
expect(linkedList.head.element).toEqual("쿠스");
expect(linkedList.head.next.element).toEqual("톰");
expect(linkedList.head.next.next.element).toEqual("마이클");
expect(linkedList.head.next.next.next.element).toEqual("미셀");
const result1 = linkedList.insert(9, "에이미");
expect(result1).toEqual(false);
linkedList.insert(0, "에이미");
expect(linkedList.head.element).toEqual("에이미");
linkedList.insert(3, "룰라");
expect(linkedList.head.next.next.next.element).toEqual("룰라");
linkedList.remove("룰라");
expect(linkedList.head.next.next.next.element).toEqual("마이클");
linkedList.remove("에이미");
expect(linkedList.head.element).toEqual("쿠스");
linkedList.removeAt(2);
expect(linkedList.head.next.next.element).toEqual("미셀");
expect(linkedList.length).toEqual(3);
expect(linkedList.indexOf("미셀")).toEqual(2);
expect(linkedList.indexOf("티라노")).toEqual(-1);
expect(linkedList.isEmpty()).toEqual(false);
expect(linkedList.size()).toEqual(3);
});활용 사례
큐는 항상 첫번째 요소만 읽고 삽입, 삭제 연산이 많으므로 큐를 구현하는데 유리하다.
확장 - 이중 연결 리스트 Doubly Linked List
양방향 리스트라고도 한다.
단방향 리스트와 달리 양방향으로 리스트 순회가 가능해진다.
HEAD포인터, TAIL포인터, 리스트요소들로 구성되어있다.
단방향 리스트에 TAIL포인터가 추가된다.
각 리스트 요소는 NEXT포인터, PREV포인터를 가지고 있다.
단방향 연결 리스트의 리스트 요소에 이전 요소의 위치정보를 가지고 있는 'PREV포인터'가 추가된다.
구현 - JavaScript에서의 이중 연결 리스트 Doubly Linked List
위에서 구현한 LinkedListNode 클래스와 LinkedList 클래스를 상속받아 필요한 부분만 추가 & 오버라이드해서 구현했다.
class DoublyLinkedListNode extends LinkedListNode {
constructor(element) {
super(element);
this._prev = null;
}
get prev() {
return this._prev;
}
set prev(node) {
this._prev = node;
}
toString() {
return `element: ${this.element} / prev: ${this.prev &&
this.prev.element} / next: ${this.next && this.next.element}`;
}
}
class DoublyLinkedList extends LinkedList {
constructor() {
super();
this._tail = null;
}
get tail() {
return this._tail;
}
set tail(node) {
this._tail = node;
}
append(element) {
const node = new DoublyLinkedListNode(element);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
let last = current;
last.next = node;
node.prev = last;
this.tail = node;
}
this.length++;
}
insert(position, element) {
if (
typeof position !== "number" ||
position < 0 ||
position > this.length - 1
) {
return false;
}
const node = new DoublyLinkedListNode(element);
if (position === 0) {
node.next = this.head;
this.head = node;
} else {
const previous = this._findPreviousByPosition(position);
node.next = previous.next;
node.prev = previous;
if (previous.next) {
previous.next.prev = node;
}
previous.next = node;
}
this.length++;
}
remove(element) {
if (!this.head) {
return null;
}
if (this.head.element === element) {
if (this.head.next) {
this.head.next.prev = null;
}
this.head = this.head.next;
if (this.head === this.tail) {
this.tail = this.head.next;
}
} else if (this.tail.element === element) {
this.tail = this.head.perv;
if (this.head === this.tail) {
this.head = this.tail.prev;
}
} else {
let current = this.head;
let previous;
while (current && !previous) {
if (current.next && current.next.element === element) {
previous = current;
}
current = current.next;
}
const target = previous.next;
if (target.next) {
target.next.prev = previous;
}
previous.next = target.next;
}
this.length--;
}
removeAt(position) {
if (
typeof position !== "number" ||
position < 0 ||
position > this.length - 1
) {
return false;
}
if (position === 0) {
this.head = this.head.next;
this.head.prev = null;
} else if (position === this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
const previous = this._findPreviousByPosition(position);
const target = previous.next;
if (target.next) {
target.next.prev = previous;
}
previous.next = target.next;
}
this.length--;
}
toString() {
let result = "### Doubly Linked List ###\n\n";
result += `[head] ${this.head.toString()}\n\n`;
let current = this.head;
while (current) {
result += `[node] ${current.toString()}\n`;
current = current.next;
}
result += `\n[tail] ${this.tail.toString()}\n`;
result += `\nlength: ${this.length}`;
return result;
}
}
// Test
it("DoublyLinkedList 클래스는 잘 동작한다.", () => {
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.append("쿠스");
doublyLinkedList.append("쉘든");
doublyLinkedList.insert(1, "바우");
doublyLinkedList.append("나비");
expect(doublyLinkedList.head.element).toEqual("쿠스");
expect(doublyLinkedList.head.next.element).toEqual("바우");
expect(doublyLinkedList.head.next.next.element).toEqual("쉘든");
expect(doublyLinkedList.head.next.next.next.element).toEqual("나비");
expect(doublyLinkedList.tail.element).toEqual("나비");
doublyLinkedList.remove("쿠스");
doublyLinkedList.remove("바우");
expect(doublyLinkedList.head.element).toEqual("쉘든");
expect(doublyLinkedList.head.next.element).toEqual("나비");
doublyLinkedList.append("복실");
doublyLinkedList.append("만수");
doublyLinkedList.append("앨리스");
doublyLinkedList.removeAt(2);
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(2);
expect(doublyLinkedList.head.element).toEqual("나비");
expect(doublyLinkedList.head.next.element).toEqual("만수");
expect(doublyLinkedList.length).toEqual(2);
});확장 - 환형 연결 리스트 Circular Linked List
마지막 리스트요소의 NEXT 포인터가 첫번째 요소를 가리킨다.
구현 - JavaScript에서의 환형 연결 리스트 Circular Linked List
위에서 구현한 LinkedList 클래스를 상속받아
요소 추가시 마지막 요소의 next포인터가 head를 향하도록 오버라이드했다.
class CircularLinkedList extends LinkedList {
append(element) {
const node = new LinkedListNode(element);
if (!this.head) {
this.head = node;
this.head.next = node;
} else {
let current = this.head;
let last;
while (current) {
if (current.next === this.head) {
last = current;
break;
}
current = current.next;
}
last.next = node;
node.next = this.head;
}
this.length++;
}
toString() {
let result = "### Linked List ###\n\n";
result += `[head] ${this.head.toString()}\n\n`;
let current = this.head;
while (current) {
result += `[node] ${current.toString()}\n`;
current = current.next === this.head ? null : current.next; // infinite loop 방지
}
result += `\nlength: ${this.length}`;
return result;
}
}
// Test
it("CircularLinkedList 클래스는 잘 동작한다.", () => {
const circularLinkedList = new CircularLinkedList();
circularLinkedList.append("쿠스");
circularLinkedList.append("빵꾸");
circularLinkedList.append("울랄라");
expect(circularLinkedList.head.element).toEqual("쿠스");
expect(circularLinkedList.head.next.element).toEqual("빵꾸");
expect(circularLinkedList.head.next.next.element).toEqual("울랄라");
expect(circularLinkedList.head.next.next.next.element).toEqual("쿠스");
});활용 사례
스트림버퍼 구현에 많이 사용된다.
- 아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
- 스기우라 켄, 『그림으로 배우는 알고리즘』, 서재원, 영진(2016)
- 이소 히로시, 『모던 자바스크립트 입문』, 서재원, 길벗(2018)
- Martin Erwig, 『그들은 알고리즘을 알았을까?』, 송원형, 영진(2017)
- Loiane Groner, 『자바스크립트 자료 구조와 알고리즘』, 이일웅, PACKT-에이콘(2015)
글쓴이쿠스, Qus
직업은 소프트웨어 개발자.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
'자료구조/알고리즘' 시리즈의 다른 이야기들