예전에 프론트엔드 개발자 기술 면접 준비를 하면서 공부했던 배열(Array)과 연결 리스트(링크드 리스트, Linked List)에 대해서 간략하게 글을 써보려고 합니다.
자료구조 공부하면서 배열과 연결 리스트는 중요한 개념이기도 하고 면접에서도 종종 나오곤 하는데요. 특히 두 자료구조의 특징 및 차이점에 대해서 물어보는 경우도 있습니다.
그래서 두 개념의 특징을 간단하게 살펴보고 자연스럽게 어떤 것들이 차이가 있는지 알아보도록 할게요.
추가로 시간복잡도(O(n))와 통상적으로 쓰이는 사례까지도 알아볼게요.
배열(Array)
배열은 정적 자료구조라고 불립니다. 그래서 배열을 만들기 위해서는 미리 크기를 정해놓게 되는데요. 그렇게 되면 해당 크기 만큼의 연속된 메모리 주소를 할당 받게 됩니다.
연속된 메모리 주소를 할당 받고 있기 때문에 데이터가 인덱스(index)라는 것을 갖게 됩니다. 우리가 array[0] 같은 식으로 배열에 접근할 때 대괄호([]) 안에 숫자가 index입니다(JavaScript 기준).
index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있는 거죠. 그러므로 접근과 탐색에 용이합니다.
하지만 크기를 미리 정해놓았기 때문에 수정하는 것이 불가능합니다. 또한 이미 크기를 정해 놓은 터라 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있습니다.
연결 리스트(Linked List)
링크드 리스트, 또는 연결 리스트는 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없습니다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않습니다.
대신 노드(Node)라는 게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있습니다. 그런 식으로 연결되어 이어진 형태인 거죠.
연결 리스트는 위에서 말한 것처럼 크기를 정해 놓지 않았기 때문에 크기의 제한이 없습니다. 그로 인해 데이터 추가, 삭제가 자유롭다는 장점이 있습니다.
반면에 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능합니다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다는 것입니다. 단점이라고 한다면 단점일 수 있는 거죠.
차이점
위에서 언급한 것을 아래 간단하게 표로 정리하면 이렇습니다.
| 배열(Array) | 연결 리스트(Linked List) |
| 정적 자료구조 | 동적 자료구조 |
| 미리 크기를 정해 놓음 | 크기를 정할 필요가 없음 |
| 연속된 메모리 주소를 할당 받음 | 연속된 메모리 주소를 할당 받지 않음 |
| 접근, 탐색 용이 | 추가, 삭제 용이 |
| index 존재 | Node 존재 |
시간복잡도
배열은 접근과 탐색이 용이하다고 했는데요. index를 가지고 있기 때문에 탐색은 O(1)의 시간복잡도를 가집니다.
삽입의 경우는 맨 뒤라고 한다면 O(1)의 시간복잡도를 가지지만 맨 뒤가 아닌 나머지는 O(n)입니다.
연결 리스트는 추가, 삭제가 용이하다고 했죠. 삽입은 맨 앞일 경우 O(1)의 시간복잡도, 맨 앞이 아닌 나머지는 O(n)입니다.
그리고 배열과 반대로 탐색은 O(n)의 시간복잡도를 가집니다.
활용 사례
배열은 정보를 저장할 때 많이 쓰는데요. 비유를 들자면 바구니 역할을 하는 것이 배열입니다. 하지만 그 바구니 안에 물건(정보)들은 일렬로 줄이 세워져 있죠.
뭔가 불규칙적인 정보를 저장하거나, 이후에 다시 사용할 정보를 저장하거나 할 때 배열을 활용합니다.
// JS Code...
const foodList = ['짜장면', '돈까스', '초밥', '김치볶음밥', '햄버거'];
const randomIndex = Math.floor(Math.random() * foodList.length);
const todayFood = foodList[randomIndex];
console.log(todayFood); // foodList 중 랜덤으로 하나의 음식 이름이 나온다.
위 처럼 간단하게 음식을 배열 안에 넣고 랜덤으로 오늘 음식을 뽑을 수도 있겠죠?
연결 리스트의 경우는 저도 실제로 앱으로 만든 경험은 없지만 음악 플레이어 앱에 이전 곡과 다음 곡이 연결되어 있듯 이런 기능이 연결 리스트로 많이 활용된다고 합니다.
또한 포토샵을 사용하신 분이라면 아실 수 있을 것 같은데 포토샵의 history 기능이 연결 리스트를 활용했다고 합니다. 포토샵은 작업을 하면 history 내역이 쌓입니다. 그래서 내가 작업한 어느 시점으로 되돌아갈 수도 있고 다시 최근으로 돌아올 수도 있는데요. 이런 것도 연결 리스트를 활용했다고 하네요.
최근댓글