Linked List(연결 리스트)

김가람휘·2022년 3월 21일
0

CS

목록 보기
13/15

Linked List

  • Linked list(연결 리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.
    • 노드(node): 데이터를 담고 있는 그릇, 주로 class로 구현되기 때문에 class라고 생각해도 상관없다.
    • 링크(link): 리스트의 순서를 유지할 수 있게 해주는 연결고리

Doubly Linked List

  • Doubly Linked List는 다음 노드 뿐만이 아니라 전 노드의 링크도 가지고 있는 연결 리스트입니다.
  • 즉, 리스트의 앞과 뒤 둘다 이동이 가능한 리스트입니다.

Circular Linked List

  • Circular Linked List의 꼬리(tail)부분이 머리(head)부분과 연결이 되어 있는 연결 리스트입니다.
  • 따라서, 리스트의 무한 반복이 가능합니다.

Array와 차이점

  • Array와 마찬가지로 순차열적으로 요소들을 저장한다는 점에서는 비슷하나 근본적으로 많은 차이를 가지고 있습니다.
    1. 배열(array)는 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적입니다. 연결리스트도 데이터를 논리적 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않습니다.
    2. 배열은 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠릅니다.(indexing) 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있습니다. 그럼으로 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능함으로 배열에 비해 원하는 데이터에 접근하는 속도가 떨어집니다.
    3. 배열은 데이터의 삽입/삭제에는 취약합니다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문입니다. 연결리스트에서 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 훨씬 쉽습니다.
    4. 동일한 양의 데이터를 저장해도 일반적으로 연결 리스트가 배열보다 더 많은 메모리를 차지하게 됩니다. (배열은 단순 데이터 저장인데 비해 연결리스트는 각 노드마다 객체를 생성해야 하기 때문이다.)

When To Use Linked List

  • 데이터 양이 많지만 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어질 경우는 배열이 유리하고, 데이터 양이 그렇게 많지 않고, 데이터의 삽입/삭제가 빈번하게 이루어질 경우에는 연결리스트를 사용하는 것이 더 유리합니다.

0개의 댓글