[자료 구조] 연결 리스트

0. 개요

연결리스트는 노드가 데이터와 포인터를 가지고 연결되어 데이터를 저장하는 자료구조

각 노드에는 다음 노드를 가리키는 포인터를 포함하고, 여기서 포인터는 마찬가지로 그 다음 노드의 주소값을 가지고 있다.

특징

• 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.
• 동적으로 새로운 노드의 삽입, 삭제가 간편하다.
• 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아 관리가 간편하다.

시간복잡도

• 탐색 : 배열처럼 인덱스로 바로 찾는 것이 아니라 노드들을 타고 가야 하기 때문에 O(n)
• 삽입,삭제,추출
  • 시작, 끝에 경우 O(1)
  • 중간에 경우 탐색하는데 시간이 걸리기 때문에 O(n)이 걸림.

1. 단방향 연결리스트(Singly Linked LIst)

위의 그림에서와 같이 한 방향으로 쭉 이어진 연결리스트를 말한다.

단일 노드가 다음과 같이 구성되어 있다.

class Node {
    Node next;
    int data;
};

 

next -> 다음 노드 주소 저장

data -> 현재 노드의 데이터

단방향 연결리스트의 경우에는 끝이 더 가까운 노드에 경우에도 O(n) 시간에 찾을 수 있다는 단점이 있다.

예를 들어 100개의 노드 중 99번째 노드를 확인해야 하면 100 -> 99가 아닌 1부터 ..99까지 탐색이 이루어져야 한다.

이를 해결하고자 양방향 연결리스트가 등장한다.

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

class Node{
   Node next;
   Node prev;
   int data;
};

next -> 다음 노드 주소 저장

prev -> 이전 노드 주소 저장

data -> 현재 노드의 데이터

 

단방향 연결 리스트와 다른점은 이전 노드의 주소를 저장한 prev 필드가 추가되었다는 점이다!

* Java에서 주로 사용하는 LinkedLIst의 경우에도 양방향 연결 리스트로 구현 됨!