장단점
장점은 데이터 추가, 삭제에 대한 시간 복잡도가 O(1)이라는 것입니다. 또한, 높은 메모리 효율성 가지고 있습니다.
하지만, Linked List는 Node라는 구조체로 이루어져 있는데 이는 Data와 Address에 대한 정보를 가지고 있습니다. Array와 달리 Address라는 정보를 추가로 저장하고 있기 때문에 데이터 당 더 많은 메모리를 사용합니다.
단점은 데이터 조회 성능에 대한 시간 복잡도가 O(n)이라는 것입니다.
왜, 그럴까?
장단점을 생각하기에 앞서 Linked List의 특징을 알아보겠습니다. Linked List는 'Node 구조체'로 이루어져 있으며, 물리적인 연속성인 아닌 '논리적인 연속성'을 지닌 자료구조입니다. 특히, Node와 논리적인 연속성이라는 키워드를 중점적으로 "왜 저런 장단점이 존재할까?"를 생각해 보겠습니다.
장점
각 Node들이 Data와 Next Address를 가진 상태로 메모리 공간에 저장되어 있습니다. 물리적으로는 연속된 형태로 저장되어 있지 않지만, Next Address를 통해 다음 Node가 저장된 주소를 저장함으로써 논리적인 연속성을 구현하고 있습니다.
이제 데이터 추가와 삭제를 진행해 보도록 하겠습니다.
추가의 경우 위 그림처럼 추가할 위치의 이전 노드와 다음 노드의 주소만 알고 있다면 가능합니다.
삭제의 경우도 마찬가지로 삭제할 노드가 가지고 있는 다음 주소를 이전 노드의 다음 주소와 교체하기만 하면 됩니다.
즉, 물리적인 제약을 받지 않는 논리적인 연속성을 가지고 있기 때문에 이전과 다음 노드의 주소만 넣어주면 어느 위치든 삽입, 삭제할 수 있어 성능이 우수합니다. 또한, 새로운 노드가 삽입될 때 메모리 공간이 할당되기 때문에 메모리를 효율적이며 자유롭게 사용할 수 있습니다.
이와 같은 이유로 데이터 추가 및 삭제에 대하여 O(1)이라는 시간 복잡도를 가지고 있으며, 효율적인 메모리 사용이 가능합니다.
단점
위 그림처럼 Node들이 다음으로 이동할 주소를 기억하고 있습니다. 즉, 145번에 저장된 노드에 접근하기 위해 '1번, 56번, 81번, 44번에 저장된 노드를 순차적으로 접근'해야 합니다. 이를 통해, 내가 가고 싶은 위치를 가기 위해선 반드시 시작 노드부터 출발해야함을 알 수 있습니다.
이와 같은 이유로 데이터 접근과 조회에 대하여 O(n)이라는 시간 복잡도를 가지고 있습니다.
정리
위 내용을 다시 한 번 정리하면 다음과 같습니다.
- Linked List는 Node로 이루어져 있으며, 이를 통해 논리적인 연속성을 가진다.
- 논리적인 연속성으로 삽입 및 삭제는 빠르지만, 조회 및 접근은 느리다.
- 데이터 삽입시 메모리 할당이 동적으로 이루어지기 때문에 메모리를 효율적으로 사용가능하다.
- 하지만, 추가로 주소도 저장하기 때문에 데이터 당 메모리 사용량은 높다.
예상 질문
Linked List는 어떤 자료구조인가요?
Node라는 구조체로 이루어진 자료구조 입니다. 또한, Node에 값과 주소를 저장하여 논리적인 연속성을 가지고 있습니다.
Linked List의 장단점은 무엇인가요?
장점은 빠른 삽입과 삭제가 가능하며 데이터 삽입시 메모리 할당이 이루어지기 때문에 메모리 효율성이 높습니다. 단점은 조회 및 접근에 대한 성능이 좋지 않습니다. 추가로, 데이터와 주소를 모두 저장하기 때문에 데이터 당 메모리 사용량은 높습니다.
