09-12. LinkedList

Q. LinkedList의 주요 특징과 사용하면 좋은 상황을 설명해주세요.

LinkedList는 노드(Node)라는 요소로 구성되어 있습니다. 노드는 데이터를 저장하는 부분과 다음 노드에 대한 포인터로 이루어져 있습니다. LinkedList는 이 노드들이 일렬로 연결된 자료구조 형태를 말합니다. 이 때 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 부릅니다. LinkedList 구조에서는 헤드 노드의 정보만 가지고 있으면 다음 노드를 찾아갈 수 있으며, 데이터의 개수에 맞춰 필요한 수의 메모리만 사용할 수 있는 장점이 있습니다. 하지만 헤드 노드의 정보만 가지고 있기 때문에 특정 위치에 있는 노드를 탐색하는데 많은 연산이 필요합니다. 이러한 특성으로 LinkedList는 데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 유용하게 사용될 수 있습니다. 예를 들어, 실시간으로 데이터가 추가되고 삭제되는 대기열 시스템이나 작업 스케줄러 등에서 효과적으로 활용될 수 있습니다.

Q. LinkedList가 ArrayList보다 삽입/삭제가 효율적인 이유는 무엇인가요?

ArrayList는 삽입/삭제를 할 때, 삽입될 데이터의 위치를 기준으로 기존의 데이터들을 뒤로 혹은 앞으로 이동하는 시프트 연산을 수행합니다. 이는 O(n)의 시간복잡도를 가집니다. 반면 LinkedList는 삽입될 노드의 해당 인덱스 이전의 노드의 다음 노드를 추가될 노드로 설정하고, 추가될 노드의 다음 노드를 인덱스 이전의 다음 노드로 설정하는 포인터 조작만 필요합니다. 삭제도 비슷한 방식으로 이전 노드의 포인터만 변경하면 되므로 O(1)의 시간복잡도로 수행할 수 있습니다. 따라서 LinkedList가 삽입/삭제 연산에서 더 효율적입니다.

Q. Singly Linked List와 Doubly LinkedList의 차이에 대해 알고 계신가요?

Singly LinkedList는 앞서 설명한대로 다음 노드를 가리키기 위한 포인터 필드(next)만을 가지고 있는 링크드 리스트입니다. Doubly LinkedList는 기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드(prev)가 추가된 형태의 링크드 리스트입니다. Doubly LinkedList는 SinglyLinkedList와 다르게 역순으로도 검색이 가능하며, 이전 노드에 대한 접근이 O(1)로 가능하다는 장점이 있습니다. 하지만 추가적인 메모리가 필요하고 삽입/삭제 시 이전 노드의 포인터도 함께 수정해야 하므로 구현이 더 복잡합니다. Doubly LinkedList는 웹 브라우저의 앞으로 가기/뒤로 가기와 같이 양방향 탐색이 필요한 경우에 주로 사용됩니다.