[자료구조/알고리즘] 연결리스트(Linked List)

1.연결리스트 (Linked List)

• 정의
  - 데이터를 링크로 연결해서 관리하는 자료구조
  - 선형 자료구조의 한 종류
• 특징
  - 자료의 순서는 정해져 있지만 메모상 연속성이 보장되지 않음
• 장점
  - 데이터 공간을 미리 할당할 필요가 없음
  - 데이터 추가/삭제가 편리함
• 단점
  - 연결구조를 위한 별도의 데이터 공간 필요
  - 연결 정보를 찾는 시간이 필요(접근 속도가 일반적으로 느림)
  - 데이터 추가, 삭제 시 앞뒤 데이터를 연결구조 재구성이 필요
• 구조
  - 노드(Node): 데이터 저장 단위로, 값과 포인터로 구성(포인터: 다음 노드나 이전 노드의 연결 정보)
  - 헤드(Head): 처음 위치에 존재하는 노드를 가르킴
  - 테일(Tail): 마지막 위치에 존재하는 노드를 가르킴
  

2.단방향 연결리스트(Singly Linked List)

• 정의
  - 각 노드가 데이터, 다음 노드를 가르키는 포인터로 이우러진 연결리스트
• 특징
  - 한 방향으로만 연결되어있기 때문에 다음 노드의 정보만 가진다
  - 마지막 노드는 Null을 가르킴
• 단점
  - 특정 노드를 찾기위해선 처음부터 찾는 위치까지 순차적으로 탐색(시간 복잡도 O(N))
  

3.양방향 연결리스트(Doubly Linked List)

• 정의
  - 각 노드 데이터, 이전 노드, 다음 노드를 가르키는 포인터로 이우러진 연결리스트
• 특징
  - 양 방향으로 연결되어있기 때문에 앞 뒤로 탐색이 가능
• 장점
  - 노드 삽입/삭제/수정이 단방향 연결리스트보다 효율적
  - 뒤에서부터 탐색이 가능

4. 원형 연결리스트(Circular Linked List)

• 정의
  - 마지막 노드가 Null이 아닌 첫번째 노드를 가르키는 연결리스트
• 특징
  - 단일 연결 리스트의 마지막 노드가 NULL이 아니라 첫 번째 노드를 가리킴
  - 이중 연결 리스트에서도 마지막 노드의 Next가 첫 번째 노드를, 첫 번째 노드의 Prev가 마지막 노드를 가리킴
• 장점
  - 리스트의 처음과 끝을 구분할 필요가 없음
• 단점
  - 리스트의 처음과 끝을 구분하지 않기 때문에 무한 루프에 빠질 가능성이 있음

5.시간복잡도

• 접근, 탐색, 삽입, 삭제 모든 과정에서 O(n)을 가진다
• 단 경우에 따라 Head나 Tail에 관한 연산의 경우 O(1)의 시간복잡도를 가진다

출처

연결리스트 이미지