[자료구조] 연결리스트 (Linked List)

연결리스트(Linked List)

연결리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.

Node란?
연결리스트에서 사용되는 하나의 데이터 덩어리이며, 데이터 & 링크 2가지 필드를 담고 있는 구조이다.

data : 노드가 담고 있는 데이터/값
next : 링크/포인터 역활, 다음 노드의 주소를 저장
* 양방향 연결 리스트의 경우 prev 포인터 (이전 노드의 주소) 추가

연결리스트에서는 통상적으로 첫번째 노드를 head 노드
마지막 노드를 tail 노드라고 부른다.

• head Node (첫번째 노드)
• tail Node (마지막 노드)

연결리스트의 특징

• 탐색은 O(n)의 시간복잡도를 가진다.
• 요소를 추가,삭제할 때는 O(1)이 소요된다.
• Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.

배열과 연결리스트의 차이점

• 배열
  • 배열은 순차적인 데이터가 들어간다.
  • random access가 가능하다.
    ex ) 배열의 n번째 원소 접근시 O(1)의 시간 복잡도 소요 - arr[n]
  • 원소의 삽입, 삭제 시 일반적으로 O(n)의 시간 복잡도 소요
    
    
• 연결리스트
  • 포인터를 사용하여 각 영역을 참조한다.
  • random access 불가능하다.
    ex ) 리스트 n번째 노드 방문시 O(n) 시간 복잡도 소요
    head 노드부터 n번째 노드까지 순회
  • 노드 삽입, 삭제 시 배열보다 빠른 일반적으로 O(1)의 시간 복잡도 소요

Singly Linked List (단일 연결 리스트)

Head에서 Tail까지 단방향으로 이어지는 연결 리스트이다. 가장 단순한 형태의 연결 리스트다.

(한쪽 방향으로만 흐르는 데이터 구조이다.)

Doubly Linked List (이중 연결 리스트)

양방향으로 이어지는 연결 리스트로 next, prev 값을 가지며, Singly Linked List보다 자료구조의 크기가 조금 더 크다.

(단일 연결 리스트와는 다르게 이전 노드, 다음 노드를 참조할 수 있는 데이터 구조이다.)

앞뒤로 탐색이 가능해 빠르다는 장점이 있지만, 두 개의 포인터를 다뤄야 하기 때문에 데이터 구조와 흐름이 복잡한 구조가 될 수 있다.

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

Singly 혹은 Doubly Linked List에서 tail이 head로 연결되는 연결리스트이다. 원형 큐 등을 만들대도 사용된다.

(head에서 tail까지 이어진 구조이다. tail의 next 값은 head이다.)

참고

코딩문codingmoon - Youtube
wikipedia