📌 링크드 리스트(Linked List)
Linked List 자료구조는 선형으로 그룹화된 데이터의 집합으로, 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 이루어진 자료구조이다.
링크드 리스트 자료구조는 연속된 공간이 아니라 흩어져 있는 공간에 노드들의 연결로 이루어진 자료구조이다. 하나의 노드에는 데이터와 다음 노드의 주소가 담겨있다. 그리고 각 노드는 다음 노드를 가리킨다. 연속된 메모리 주소가 아니기 때문에 직접 주소 값을 가지고 있어야 다음 노드에 접근할 수 있다.
배열과 링크드 리스트를 메모리에 표시하면 아래 이미지와 같다.
각각의 메모리 주소는 순차적이지 않고 다음 메모리 주소를 가리킨다. 마지막노드는 다음을 가리킬 곳이 없으므로 새로 추가되기 전까지는 null을 가리킨다.
📌 링크드 리스트의 구조
링크드 리스트는 포인터(Pointer)와 데이터(Data)가 담긴 노드(Node)라는 객체로 구성되어 있다.
- 노드(Node)
데이터를 전송, 수신 및 전달할 수 있는 물리적인 공간이다.
노드는 포인터(Pointer)와 데이터(Data)로 구성되어 있다. - 포인터(Pointer)
다음 노드, 혹은 이전 노드의 주소를 가리키는 변수를 말한다. - 데이터(Data)
링크드 리스트에 저장되는 데이터이다
✔️ 링크드 리스트의 종류
- 단일 연결 리스트(Single Linked List)
각 노드에 자료 공간과 한 개의 포인터 공간이 있으며, 각 노드의 포인터는 다음 노드를 가리킨다. - 이중 연결 리스트(Double Linked List)
단일 연결 리스트와 다르게 포인터 공간이 두 개로, 각 노드는 이전 노드와 다음 노드를 가리킨다. - 원형 연결 리스트(Circular Linked List)
단일 연결 리스트의 구조와 동일하지만, 원형 연결 리스트는 마지막 노드의 다음 노드가 처음 노드를 가리킨다.
📌 링크드 리스트의 특징
✔️ 노드의 추가와 삭제가 빠르고 쉽다.
배열은 메모리 순서가 정해져 있어서 값을 추가하거나 삭제할 때 메모리에 재할당을 해야하지만 링크드 리스트는 순서가 지정되지 않은 특성 때문에 데이터를 담은 노드를 어디에도 손쉽게 추가하거나 삭제할 수 있다.
배열은 추가하거나 삭제하는 경우, 때에 따라서 시간 복잡도가 많이 걸린다.
배열은 중간에 데이터를 추가하고 싶을 때 제일 마지막 인덱스를 새로 만들어서 삽입하고자 하는 인덱스까지의 모든 데이터를 한 칸씩 이동한 다음에 원하는 인덱스에 값을 추가할 수 있다.
가장 마지막 인덱스에 데이터를 추가할 때는 가장 빠른 O(1)의 시간 복잡도를 보이지만 0번 인덱스에 데이터를 추가하는 경우 모든 데이터를 오른쪽으로 옮겨야 하므로 최악의 경우 O(N)의 시간복잡도를 가진다.
삭제는 추가의 반대 과정으로 동작한다. 배열은 마지막 요소의 수정은 빠르지만, 맨 앞의 요소의 수정은 가장 오래 걸리게 된다.
링크드 리스트에 데이터를 추가하는 경우
- 41번 노드는 새로 33번 노드의 주소를 가리킨다.
- 새롭게 추가된 33번 노드는 다음 주소인 25를 가리킨다.
링크드 리스트에서 데이터를 삭제하는 경우
- 25번 노드는 삭제될 노드의 다음 주소를 가리킨다.
- 삭제될 노드는 자바의 가비지 컬렉터가 수거해간다.
✔️ 노드의 값을 찾으려면 최대 전체를 순회한다.
링크드 리스트의 정보는 헤드 노드(Head Node)에서 주어지는데, 헤드 노드는 헤드 노드의 값과 뒤로 붙은 노드의 개수(size), 그리고 다음 노드의 주소만을 정보로 주어준다. 때문에 다음 노드의 요소 정보를 전혀 알 수 없다. 이러한 이유로 링크드 리스트에서 인덱스에 접근하기 위해선 헤드 노드로부터 탐색 인덱스만큼 순회해야 한다.
헤드 노드에 있는 값은 O(1)의 시간 복잡도를 가지지만, 마지막 요소의 값에 접근하기 위해서는 요소의 개수만큼 순회해야 하기 때문에 최악의 경우 O(N)의 시간 복잡도를 가진다.
📌 링크드 리스트의 활용
- 삽입과 삭제가 중요한 곳에 활용된다.
join, split method처럼 데이터의 삽입/삭제가 중요한 메서드의 구현에도 활용할 수 있다. - 동적 기억장소 관리(Dynamic Storage Management)
실행되는 작업에 필요한 크기만큼의 메모리를 할당하는 방법에 활용된다. - Gabage collection
참조자료형의 데이터 타입을 관리하는 알고리즘에 활용된다. - 해시테이블 충돌 해결
해시테이블의 충돌 시 해결 방법 중 chaning 방법을 사용할 때 링크드 리스트를 활용한다.
댓글