개념
Linked List(연결 리스트)는 Node들이 연결되어 리스트 형태를 갖추고 있는 data structure 로,
Node는 data(value)와 link(reference/address) 를 가지고 있으며 이전 Node의 reference/address 는 다음 노드의 data(value)를 가리킨다.
전체 리스트 중 첫번째 Node를 ‘head’, 마지막 Node를 ‘tail’ 이라고 지칭한다.
종류
- 단순 연결 리스트(Singly Linked List)
- 링크가 단방향으로 흘러가는 리스트 구조체
- 각 노드(Node)는 하나의 링크로 연결되어 있어 다음 노드를 바라보며, 이전 노드에 접근하려면 첫 번째 노드부터 재검색 해야한다.
- 이중 연결 리스트(Doubly Linked List)
- 노드가 양방향으로 흘러가는 리스트 구조체
- 각 노드는 앞 뒤로 연결되어 있어 이전 노드에 접근이 가능하지만, 2개의 address를 가지기 때문에 저장공간이 추가로 필요하다.
- 원형 연결 리스트(Circular Linked List)
- 링크가 단방향으로 흘러가며, 마지막 노드(tail)가 첫번째 노드(head)를 바라보는 구조이다.
배열 vs 연결리스트
메모리의 할당과 데이터접근, 시간복잡도 관점에서 설명할 수 있다.
-
메모리 할당
- 배열은 데이터를 선언함과 동시에 메모리가 Stack 영역에 할당되며 이를 정적메모리할당 이라고 한다. 또한 인접한 memory 영역에 저장하기 때문에 메모리→캐시로 데이터를 전달할 때 이들의 처리속도가 빠르다.
- 연결리스트는 새로운 Node를 추가할 때 Heap 영역에 할당되며 이를 동적메모리할당 이라고 한다. 배열과 달리 memory를 곳곳에 저장하는 연결리스트의 경우, 메모리→케시로 데이터를 전달할 때 처리속도가 느리다.
-
데이터 접근
- 배열은 Random Access(랜덤 접근)형식으로, 데이터가 위치한 index 만 알고 있다면 바로 접근이 가능하다. - O(1)
- 연결리스트는 Sequential Access(순차 접근)형식으로, 특정 데이터에 접근하려면 처음 노드부터 순서대로 찾아야한다. -O(n)
-
시간 복잡도
- 배열에서 데이터 탐색 시 특정 위치에 index를 통해 직접 접근이 가능하기 때문에, O(1)의 시간복잡도를 가진다.
- 연결리스트에서 데이터 탐색 시 첫번째 노드부터 순차적으로 찾아야하기 때문에, O(n)의 시간복잡도를 가진다.
- 이와 달리 데이터의 추가/삭제의 경우 배열은 O(n), 연결리스트는 O(1)로 정반대의 결과를 확인할 수 있다. 이유를 살펴보자.
** 데이터 삽입
데이터 삽입의 경우, 삽입하려는 위치에서 기존노드가 바라보던 링크를 끊고 이전 요소의 address와 추가할 노드의 value 바라보게 한 뒤 추가하는 노드의 address와 다음 노드를 연결시킨다.
즉, 앞 노드 -> 추가할 노드 -> 다음 노드 를 링크로 이어주는 작업만 수행하기 때문에 O(1)의 시간 복잡도 로 표현한다.
** 데이터 삭제
데이터 삭제를 할 때에는, 삭제하려는 노드의 이전 노드의 address와 다음 노드의 value 를 바라보게 한다. 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드만 링크로 연결해주면 되기 때문에 O(n)의 시간 복잡도로 표현한다.
연결리스트는 추후에 학습할 Tree 와 Graph의 기초가 된다고 하니, 개념은 물론 리스트 알고리즘 문제를 여러개 풀어서 코드 구현을 자유자재로 할 필요가 있다는 생각이 든다.
쉽게 얻을 수 있는 것들은 처음엔 좋은 것 같지만 돌아보면 그러지 않다.
반면, 힘들고 어려운 일은 그 과정은 고통스럽지만 오래 남는다.
나에게 코딩이란 그런 존재인 듯 하다. 과정이 힘들지만 해냈을 때의 성취감과 가치는 무엇과도 바꿀 수 없는, 밉지만 미워할 수 없는..
참조
