들어가며
연결 리스트를 시작으로 자료구조를 본격적으로 공부하려 합니다. 자료구조를 제대로 공부해야만 훗날 근무를 할 때, 더 좋은 코드를 작성할 수 있다고 믿습니다. 그렇다면 연결 리스트는 무엇인지, 언제, 어떻게 쓰이는지 등을 차근차근 공부해보겠습니다.
연결 리스트는 어디에 쓰일까?
연결 리스트는 자바스크립트에서 어떻게 사용할 수 있을까요? 본격적으로 살펴보기 앞서, 연결 리스트에 대해 간단하게 알아보겠습니다. 연결 리스트는 큐와 비슷하게도 무언가를 기다리기 위해 차례대로 줄을 서 있는 구조라고 생각하면 편할 것 같습니다. 이런 연결 리스트는 웹 브라우저의 history 관리를 할 때 사용됩니다. 웹 브라우저에서 여러 사이트들을 돌아다니면, 방문 history에 방문 기록들이 연결 리스트와 같은 구조로 저장됩니다. 연결 리스트 자료구조를 통해 사용하고 있던 사이트에서 다른 사이트로 넘어갈 때, 이전 사이트의 정보를 가지고 넘어갑니다. 따라서 우리가 브라우저에서 뒤로 가기, 앞으로 가기 버튼을 누르면 우리가 열람했던 사이트들로 이동할 수 있습니다. 그렇다면 연결 리스트란 과연 무엇일까요? 본격적으로 알아보겠습니다.
Linked List (연결 리스트)
연결 리스트는 여러 노드들이 연결되어있는 구조입니다. 여기서 노드란, data와 link 필드를 갖고 있는 구조체입니다. 노드는 link를 통해 다음 노드에 접근할 수 있으며, 노드들은 다음에 올 노드의 정보를 갖고 있습니다. 이런 연결 리스트의 구조에서 맨 앞을 Head라 하며 맨 마지막을 Tail이라 합니다. 이런 연결 리스트의 시간 복잡도는 어떠할까요?
연결 리스트의 Big-O (시간 복잡도)
연결 리스트를 활용하여 자료를 삽입하고 삭제하고 검색한다면 시간 복잡도는 어떻게 될까요?
| Insertion | O(1) |
| Deletion | O(1) |
| Search | O(n) |
먼저 삽입을 한다고 생각해보겠습니다. 연결 리스트에 자료를 삽입할 때는 기존의 링크를 끊은 다음 추가할 위치의 이전 요소의 꼬리와 삽입할 자료를 연결합니다. 그리고 추가할 요소의 꼬리와 다음 요소를 연결해주면 됩니다. 이때 오직 앞 요소와 다음 요소를 연결시켜주는 동작만 수행되므로 시간 복잡도는 O(1)으로 표현할 수 있습니다.
만약 삭제를 한다면, 삭제하고자 하는 요소의 이 전 요소의 꼬리를 다음 요소를 연결시켜주면 됩니다. 삭제하고자 하는 요소의 이 전 요소와 다음 요소를 연결시켜주는 동작이 수행되므로 시간 복잡도는 O(1)로 표현할 수 있습니다.
만약 연결 리스트에서 특정 자료를 검색하고 싶다면 맨 앞의 head에서부터 순차적으로 자료를 찾아야 합니다. 연결 리스트의 각 노드들은 다음 요소들의 정보를 갖고 있기 때문에 맨 앞의 리스트에서부터 그다음의 노드들로 순차적으로 검색해야 합니다. 이때의 시간 복잡도는 O(n)으로 표기할 수 있습니다.
지금까지 연결 리스트의 특징을 알아봤는데, 연결 리스트에도 다양한 종류의 연결 리스트가 존재합니다. 다음에는 다양한 종류의 연결 리스트에 대해 알아보겠습니다.
연결 리스트의 종류
연결 리스트에는 다양한 종류가 존재합니다. 단방향 연결 리스트에서 개선된 자료구조를 살펴보겠습니다.
1. Doubly Linked List (이중 연결 리스트)
연결 리스트에서 탐색을 할 때, 뒤쪽의 원소를 검색하면 loop를 돌아야 하기 때문에 탐색 속도가 많이 느려지게 됩니다. 이 문제를 해결하려면 뒤쪽 원소들도 빠르게 검색할 수 있는 이중 연결 리스트 구조를 활용하면 됩니다.
이중 연결 리스트는 기존 단일 연결 리스트와 다르게 2개의 주소 칸을 갖습니다. 추가된 주소 칸은 이전 원소의 주소를 기억하고 Head뿐만 아니라 가장 끝 원소인 Tail의 주소도 기억합니다. 만약 사용자가 특정 인덱스의 탐색을 요청하면 해당 인덱스가 전체 리스트의 중앙보다 앞쪽인지 뒤쪽인지 판단하여 만약 앞쪽이라면 Head를 이용하여 탐색하고 뒤쪽이라면 Tail을 이용하여 탐색합니다. 그러나 주소를 2개 저장해야 해서 저장공간이 추가로 더 필요하다는 단점이 있습니다.
2. Circular Linked List (원형 연결 리스트)
연결 리스트는 항상 앞에서만 탐색을 수행해야 합니다. 만약 이중 연결 리스트 구조를 적용해도 앞 혹은 뒤에서만 탐색을 수행할 수 있습니다. 그러나 개발자 입장에서 어떤 순간에는 작업하던 곳에서 이어서 탐색을 진행하고 싶을 수 있습니다. 이러한 문제를 해결하기 위해 앞과 뒤가 연결되어있고 마지막 작업한 위치를 Head이자 Tail로 설정된 Circular Linked List (원형 연결 리스트) 구조가 있습니다.
원형 리스트를 사용하면 굳이 Head가 어디인지, Tail이 어디인지 신경 쓸 필요가 없습니다. 때문에 마지막 작업하던 위치에서 이어서 탐색, 삽입, 삭제 등의 연산 등을 곧바로 수행할 수 있다는 장점이 있습니다. 그러나 데이터 순서의 개념이 모호해지고, 때문에 인덱스를 이용한 탐색이 어렵다는 단점이 있습니다.
이렇게 연결 리스트를 공부해보면서, 연결 리스트와 배열의 차이점은 무엇이 있는지 알아보고 싶었습니다. 배열과 연결 리스트는 어떤 차이점이 있고 어떤 특징이 있는지 알아보겠습니다.
배열 vs 연결 리스트 차이
먼저 배열은 메모리를 연속적으로 저장한다는 특징을 갖고 있습니다. 또한 배열은 n번째 원소를 접근할 때 바로 접근할 수 있습니다. 하지만 메모리 사용이 비효율적이며, 배열 내의 데이터 추가 및 삭제의 시간 복잡도가 O(n)이라는 단점이 있습니다. 반대로 연결 리스트는 메모리를 효율적으로 사용할 수 있고 삽입, 삭제에 대해 효율적으로 할 수 있다는 장점들도 있지만, 많은 단점들을 갖고 있습니다. 그렇다면, 연결 리스트는 어떤 단점들이 존재할까요? 이에 대해 알아보겠습니다.
캐싱에 적합하지 않은 구조
연결 리스트의 탐색은 loop를 돌아야 하기 때문에 O(n)의 시간 복잡도를 갖고 배열 리스트의 탐색은 O(1)의 시간 복잡도를 갖습니다. 그러나 실제로 시간을 계산해보면 배열 리스트의 연산이 연결 리스트에 비해 압도적으로 빠릅니다. 그 이유는 무엇일까요?
그 이유는 컴퓨터 안에 있는 캐시(Cache)라는 저장 공간 때문입니다. CPU는 메인 메모리에 적재(load)된 소스코드를 한 줄씩 읽어서 처리하는데 메인 메모리(RAM)의 경우 프로세서(CPU)에 비해 데이터 처리 속도가 압도적으로 느립니다. 때문에 CPU에서 작업을 완료해도 메인 메모리에 있는 데이터나 소스코드가 전송되지 않아서 CPU가 오랜 시간 대기하는 경우가 생깁니다. 이러한 문제를 해결하기 위해 이 둘 사이에 캐시라는 저장공간을 만들고 메인 메모리에 적재된 정보 중 일부를 캐시에 미리 적재합니다. 캐시는 SRAM 기반으로 DRAM 기반의 메인 메모리보다 훨씬 빠르다는 특징이 있습니다. CPU는 메인 메모리가 아닌 캐시에서 정보들을 가져오게 되고 이러한 캐싱 방식을 이용하면 CPU가 쉬는 시간을 극도로 줄일 수 있습니다.
배열 리스트의 경우 데이터들이 연속된 메모리 공간에 저장되어 있습니다. 때문에 메모리에서 캐시로 데이터를 넘길 때 이 데이터들이 한 번에 같이 넘어가서 CPU가 매우 빨리 이들을 처리할 수 있는데, 연결 리스트의 경우 데이터를 메모리 곳곳에 저장한 뒤 이들을 주소로만 연결해놓은 구조이기 때문에 데이터가 캐시로 한 번에 넘어오지 못하고 CPU가 이들이 넘어올 때까지 기다려야 하므로 처리속도가 매우 느려지게 됩니다.
복잡한 연산에 따른 오버헤드 발생
일반적으로 배열 리스트의 연산들보다 연결 리스트의 연산들이 훨씬 복잡합니다. 때문에 모든 연산을 수행할 때 더 많은 명령어가 필요하고 때문에 더 많은 오버헤드가 발생하게 됩니다. 이러한 이유로 알고리즘의 시간 복잡도 이외에도 추가적인 시간들이 소모됩니다.
주소 저장으로 인한 공간 낭비
연결 리스트의 경우 데이터 이외에도 주소에 대한 정보를 반드시 가지고 있어야 하기 때문에 주소에 대한 용량이 소모됩니다. 일반적으로 정수형 리스트의 경우 데이터(integer), 주소(integer)를 저장하기 때문에 배열 리스트와 비교하여 2배의 용량이 필요합니다.
이렇게 연결 리스트의 단점들에 대해 알아봤습니다. 그렇다면, 연결 리스트는 어떻게 구현해볼 수 있을까요?
JS로 Linked List 구현하기
먼저 Linked List에 대한 ADT를 먼저 알아봅시다.
* ADT(Abstract Data Type)이란?
ADT란 추상 자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것입니다.
| ADT | 종류 | 설명 |
| element | 변수 | 요소가 저장되는 변수 |
| next | 변수 | 다음 노드를 저장하는 변수 |
| head | 변수 | Node 객체가 저장 |
| find | 함수 | item을 element로 갖는 node 찾기 |
| findPrevious | item을 element로 갖는 node를 가리키는 node를 찾기 | |
| append | newElement를 element로 갖는 node를 뒤에 추가 | |
| insert | item을 element로 갖는 node 뒤에 newElement를 element로 갖는 node 추가 | |
| toString | 연결 리스트의 요소들을 출력 | |
| remove | item을 element로 갖는 node 삭제 |
그렇다면, 위의 ADT를 활용하여 자바스크립트로 Linked List를 구현해보겠습니다.
class Node {
constructor(element){
this.element = element;
this.next = null;
}
}
class LinkedList {
constructor(){
this.head = new Node("head");
}
append(newElement) {
let newNode = new Node(newElement); //새로운 노드 생성
let current = this.head; // 시작 노드
while(current.next != null) { // 맨 끝 노드 찾기
current = current.next;
}
current.next = newNode;
}
insert(newElement, item) {
let newNode = new Node(newElement); //새로운 노드 생성
let current = this.find(item); // 삽입할 위치의 노드 찾기
newNode.next = current.next; // 찾은 노드가 가리키는 노드를 새로은 노드가 가리키기
current.next = newNode; // 찾은 노드는 이제부터 새로운 노드를 가리키도록 하기
}
remove(item) {
let preNode = this.findPrevious(item); // 삭제할 노드를 가리키는 노드 찾기
preNode.next = preNode.next.next; // 삭제할 노드 다음 노드를 가리키도록 하기
}
find(item){
let currNode = this.head;
while(currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
findPrevious(item) {
let currNode = this.head;
while(currNode.next != null && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
}
toString() {
let array = [];
let currNode = this.head;
while(currNode.next !== null){
array.push(currNode.next.element);
currNode = currNode.next;
}
return array
}
}
let linkedList = new LinkedList();
linkedList.insert("A", "head");
linkedList.insert("B", "A");
linkedList.insert("C", "B");
linkedList.remove("B");
linkedList.append("D");
linkedList.append("E");
console.log(linkedList.toString())
append 메서드를 활용해서, 맨 뒷 노드에 새로운 노드를 추가할 수 있습니다. insert 메서드를 활용하면 추가하고 싶은 노드 부분에 새로운 노드를 추가할 수 있습니다. remove 메서드를 활용하면, 노드 간의 연결을 끊어버리며, toString 메서드를 활용하면, 현재 연결 리스트에 있는 노드의 모음을 볼 수 있습니다.
지금까지는 한쪽 방향으로만 노드를 추가하고, 삭제하고, 삽입할 수 있었다면, 이제는 양방향으로 접근할 수 있는 방법에 대해 알아보겠습니다.
JS로 양방향 Linked List 구현하기
기본적인 연결 리스트는 기존의 노드들이 next만을 이용해서 한쪽 방향으로만 접근했다면, 양방향 연결 리스트는 노드가 앞(prev), 뒤(next)로 접근할 수 있게 하는 연결 리스트입니다.
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
class LinkedList {
constructor() {
this.head = new Node("head");
}
find(item) {
let currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
if (current.next == null) {
newNode.next = null;
newNode.prev = current;
current.next = newNode;
} else {
newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;
}
}
remove(item) {
let currNode = this.find(item);
if (currNode.next !== null) {
currNode.prev.next = currNode.next;
currNode.next.prev = currNode.prev;
currNode.next = null;
currNode.prev = null;
}
}
}
const linkedList = new LinkedList();
linkedList.insert("Seoul", "head"); //head->Seoul
linkedList.insert("Busan", "Seoul"); //head->Seoul->Busan
linkedList.insert("Daegu", "Seoul"); //head->Seoul->Daegu->Busan
linkedList.insert("Incheon", "Busan"); //head->Seoul->Daegu->Busan->Incheon
linkedList.remove("Busan"); //head->Seoul->Daegu->Incheon
단방향 연결 리스트와는 다르게, 양방향 연결 리스트의 경우 삽입과 삭제를 구현한 부분에서 next와 prev 부분이 추가된 것을 확인할 수 있습니다. 각 노드별로 이전과 다음 부분을 고려해서 코드를 구성해야 하기에 메모리 저장공간이 더 필요하다는 단점이 있습니다.
JS로 원형 Linked List 구현하기
원형 연결 리스트는 노드의 next가 null을 가리키는 것이 아니라 head노드를 다시 가리켜서 순환 구조를 갖는 연결 리스트입니다.
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
class LinkedList {
constructor() {
this.head = new Node("head");
this.head.next = this.head;
}
find(item) {
let currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
if (current.next !== null) {
newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;
}
}
remove(item) {
let currNode = this.find(item);
if (currNode.next !== null) {
currNode.prev.next = currNode.next;
currNode.next.prev = currNode.prev;
}
}
}
const linkedList = new LinkedList();
linkedList.insert("Seoul", "head"); //head->Seoul->head
linkedList.insert("Busan", "Seoul"); //head->Seoul->Busan->head
linkedList.insert("Daegu", "Seoul"); //head->Seoul->Daegu->Busan
linkedList.insert("Incheon", "Busan"); //head->Seoul->Daegu->Busan->Incheon
linkedList.remove("Busan");
console.log(linkedList);
원형 연결 리스트의 경우 처음 생성자 함수를 활용할 때 이중 연결 리스트와는 head와 head.next를 설정하는 부분에서 차이가 있습니다.
마치며
자료구조를 처음 공부합니다. 공부하는데 많은 시간이 걸렸습니다. 이해가 안 되는 것들이 많아서 더 그랬던 것 같습니다.
하지만 제대로 공부하는 과정이라고 생각합니다. 저는 어렵게 공부하면 공부한 내용을 잊지 않는다고 믿고 있습니다. 느리더라도, 포기하지 않고 꾸준히 앞으로 나아가겠습니다. 지켜봐 주세요. 감사합니다.
참고
[자료 구조] Data Structure - (1) Stack / Queue / Linked List
자료 구조는 코딩과는 별로 상관없는 것처럼 보일 수도 있겠지만 사실 프로그래밍에 있어서 매우 중요한 부분을 차지한다. 내가 어떠한 프로그램을 구현할 때, 혹은 어떤 알고리즘 문제를 해결
im-developer.tistory.com
연결 리스트 with C++ (Part I)
연결리스트의 특성과 작동방식
medium.com
ES6 자료구조 연결리스트(LinkedList) 구현하기(이중연결리스트, 원형연결리스트) 그리고 의문점..
ES6로 연결리스트(LinkedList) 만들기 연결리스트라는 자료구조를 구현해본다. 기존 배열은 단점이 있다. 자바스크립트에서는 아니지만 다른 언어에서 배열은 길이를 자유롭게 늘리고 줄이기 어렵
jeong-pro.tistory.com
[자바스크립트] LinkedList 연결 리스트 클래스
Linked List 클래스 연결 리스트란? 연결 리스트는 각 데이터들을 포인터로 연결하여 관리하는 자료구조입니다. 연결 리스트에서는 노드라는 새로운 개념이 나오는데, 각 노드는 데이터를 저장하
dororongju.tistory.com
[실전 알고리즘] 0x04강 - 연결 리스트
안녕하세요, 바킹독이에요. 배열은 복습 잘 하셨나요? 이번 시간에는 연결 리스트라는 것을 같이 배워보겠습니다. 배열에서 한 것 처럼 연결 리스트가 무엇인지 알아보고, 같이 구현해볼 것입니
blog.encrypted.gg
[javascript] 단순 연결리스트 만들기 linked-list
javascript의 배열은 array-list라는 것의 형태를 띄고 있어 배열의 크기 존재하지 않는다. 그런데 c 같은 언어들은 배열의 크기가 존재하기에 한 배열을 유한하게 밖에 사용 할 수 없다. 그래서 개발
hokeydokey.tistory.com
리스트 (3) - 연결리스트 (Linked List)
1. Linked List (연결리스트) 연결리스트는 기존 배열리스트가 삽입, 삭제시 배열을 새로 만들고 옮겨담아야 한다는 문제를 해결하기 위해 등장하였다. 아래의 그림을 보면 연결리스트의 동작을 쉽
gusdnd852.tistory.com
'자료구조' 카테고리의 다른 글
| [자료구조] 스택 with JavaScript (0) | 2021.11.07 |
|---|---|
| [자료구조] 해시테이블 with JavaScript (1) | 2021.10.31 |
| [자료구조] 시간복잡도 with JavaScript (1) | 2021.09.02 |
