🧷 LinkedList
LinkedList는 List를 상속해서 만들어진 클래스이다. 위 이미지는 LinkedList의 가장 기본적인 '단방향 링크드 리스트'를 표현한 것이다.
LinkedList는 ArrayList와 다르게 데이터들이 연속적인 메모리 공간에 저장되지 않고, 노드들이 연속성 없이 메모리 이곳 저곳에 생성이 되게 된다.
이곳 저곳에 노드들이 생성되지만 현재 노드는 다음 노드의 주소값을 갖고 있어서 이들은 연결성을 갖게 된다.
🤔 LinkedList는 왜 사용할까?
LinkedList를 사용하는 이유는 ArrayList와 비교해보면 알 수 있다.
위에서도 이야기했지만, ArrayList는 연속적인 메모리 공간에 값들이 저장되는 특징을 갖고 있어서 데이터의 생성, 수정, 삭제등등의 작업이 일어나면 메모리 공간을 늘렸다가 줄였다가하는 작업이 일어나게 된다. 또, 배열 중간에 값이 추가되게 되면 공간을 마련하기 위해 삽입될 위치 이후에 존재하는 데이터들을 한 칸씩 밀기(Shift)도 한다.
즉, 데이터 뿐만 아니라 메모리 공간을 관리하는 비용도 발생한다는 것이다.
이런 '공간'적인 측면에서 LinkedList는 ArrayList보다 매우 자유롭다고 할 수 있다. 공간이 연속적일 필요 없이 현재 노드는 다음 노드 또는 이전 노드의 주소값만 들고 있으면 되는 것이다.
데이터의 생성, 수정, 삭제등등의 작업이 일어나면 각 노드의 주소값들만 알맞게 추가 또는 수정해주면 된다.
결론적으로, LinkedList는 배열이 필요한데, 그 크기도 가늠할 수 없고 언제 필요할지도 모르는 극한(?)의 유연함이 요구되는 상황에서 사용이 된다.
Map계열의 자료구조에서도 하나의 Key값에 대해서 여러 값의 관리가 필요할 경우 LinkedList를 사용한다. 얼만큼의 Key에서 중복이 발생할지도 모르고, 얼만큼의 값들을 관리해야할지도 알 수 없는 '유연함'이 필요한 상황인 것이다.
📌 인덱스 또는 특정 값 검색하는 경우, 해당 인덱스 또는 값이 어떤 노드를 의미하는지 탐색해야해서 ArrayList에 비해서 특정 요소에 바로 접근하는 성능은 떨어진다.
🧐 LinkedList의 확장
CircularLinkedList
CircularLinkedList는 Tail에서 Head가 연결되어 있다는 특징을 갖고 있다.
이로써 어떠한 노드든 '시작점'이 될 수 있다는 장점을 갖게 된다. 반복문을 돌거나 List를 훑어야하는 상황에서 아무 노드에서나 시작을 할 수 있는 것이다.
이러한 특징으로 인해서 Queue와 같은 역할을 하는 기능 또는 DB에서 자주 사용이 된다. 가장 최근에 Queue에 들어온 데이터만 바라보면, 방금 들어온 데이터와 가장 처음에 있는 데이터를 바로 알 수 있기 때문이다.
이러한 특징으로 인해서 오히려 무한 Loop에 빠질 위험이 비교적 높은 자료구조이기도 하다. 반복문의 처리를 원활히 해주지 않으면 계속 뱅글뱅글 돌아버릴 수가 있는 것이다. 🥲
DoublyLinkedList
DoublyLinkedList는 한국어로 양방향 연결 리스트라고 한다. LinkedList는 다음 노드의 주소값만 갖고 있었던 것에 반해 DoublyLinkedList는 이전 노드의 주소값도 갖고 있는 것이 주요한 특징이다.
이러한 특징은 탐색의 효율성이 올라간다는 장점이 있다. LinkedList는 데이터 탐색을 하려면 무조건 Head 노드부터 단방향으로 탐색하는 수 밖에 없다.
하지만 DoublyLinkedList는 '정방향'과 '역방향'으로 탐색할 수 있다. 데이터를 탐색할 때, Head 노드부터 정방향으로 탐색하는 것과 Tail 노드부터 역방향으로 동시에 수행할 수 있는 것이다.
예시로, List의 크기가 20이라고 했을 때, LinkedList는 최대 20만큼 시간을 탐색하게 되는데, DoublyLinkedList는 최대 20/2만큼의 시간이 소요되는 것이다.
그래서, LinkedList보다 메모리도 많이 쓰이고, 복잡한 구조를 갖고 있다는 단점이 있지만, 탐색 속도가 2배 더 빠를 수 있다는 이유로 실질적으로는 가장 많이 사용되는 자료구조이다.
CircularDoublyLinkedList
CircularLinkedList와 DoublyLinkedList를 합친 궁극의(?) LinkedList이다. 연결이 끊어지지 않으면서 탐색을 양방향으로 할 수 있다는 장점을 갖고 있는 자료구조이다.
위에서 소개한 LinkedList의 장점들을 모두 갖고 있지만, 그만큼 메모리가 많이 쓰이며 복잡하다고 할 수 있다. 그래서 꼭 필요한 상황에서만 사용되는 것 같다.
예를 들자면, 아래와 같은 기능을 구현하고자 할 때 많이 사용된다고 한다.
- 음악 플레이리스트
- Undo, Redo 기능 구현
- Cache 메모리 관리
