Linked List
- Linked list(연결 리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.
- 노드(node): 데이터를 담고 있는 그릇, 주로 class로 구현되기 때문에 class라고 생각해도 상관없다.
- 링크(link): 리스트의 순서를 유지할 수 있게 해주는 연결고리
Doubly Linked List
- Doubly Linked List는 다음 노드 뿐만이 아니라 전 노드의 링크도 가지고 있는 연결 리스트입니다.
- 즉, 리스트의 앞과 뒤 둘다 이동이 가능한 리스트입니다.
Circular Linked List
- Circular Linked List의 꼬리(tail)부분이 머리(head)부분과 연결이 되어 있는 연결 리스트입니다.
- 따라서, 리스트의 무한 반복이 가능합니다.
Array와 차이점
- Array와 마찬가지로 순차열적으로 요소들을 저장한다는 점에서는 비슷하나 근본적으로 많은 차이를 가지고 있습니다.
- 배열(array)는 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적입니다. 연결리스트도 데이터를 논리적 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않습니다.
- 배열은 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠릅니다.(indexing) 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있습니다. 그럼으로 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능함으로 배열에 비해 원하는 데이터에 접근하는 속도가 떨어집니다.
- 배열은 데이터의 삽입/삭제에는 취약합니다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문입니다. 연결리스트에서 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 훨씬 쉽습니다.
- 동일한 양의 데이터를 저장해도 일반적으로 연결 리스트가 배열보다 더 많은 메모리를 차지하게 됩니다. (배열은 단순 데이터 저장인데 비해 연결리스트는 각 노드마다 객체를 생성해야 하기 때문이다.)
When To Use Linked List
- 데이터 양이 많지만 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어질 경우는 배열이 유리하고, 데이터 양이 그렇게 많지 않고, 데이터의 삽입/삭제가 빈번하게 이루어질 경우에는 연결리스트를 사용하는 것이 더 유리합니다.
