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

연결 리스트(Linked List)

연결 리스트는 data와 link로 이루어진 여러 개의 묶음이 이어져있는 형태이다.

출처 - 나무위키

 

연결리스트를 사용하기 위해, C언어 기준으로 우리는 구조체를 사용한다.

typedef struct _node
{
    int data; // 데이터를 저장하는 변수
    struct _node *link; // 다음 노드를 가리킬 링크
} Node;

 

기본적으로 위의 형태와 같이 작성한다. 

data는 사용자의 필요에 따라 int형 값이 아닌 다른 변수형으로 선언해도 무방하다.

그리고 다음 노드와의 연결을 위한 link 가 필요한데, 이 link는 우리가 선언한 구조체를 그대로 자료형으로 사용하여 포인터 형식으로 선언한다.

말 그대로 다음 노드를 "가리키는" 것이 목적이기 때문에 포인터 변수로 선언한다.

 

 

 

 

연결 리스트의 종류는 아래와 같다.

 

1. 단순 연결리스트 (Singly Linked List)

https://hudi.blog/ds-linked-list/

다음 노드에 대한 참조값만을 가지고 있는 가장 기본적인 연결리스트이다.

반대방향의 값을 탐색하는 데 어려움이 있다.

 

 

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

https://www.google.com/url?sa=i&url=https%3A%2F%2Fvelog.io%2F%40717lumos%2F%25EC%259E%2590%25EB%25A3%258C%25EA%25B5%25AC%25EC%25A1%25B0-%25EC%2597%25B0%25EA%25B2%25B0%25EB%25A6%25AC%25EC%258A%25A4%25ED%258A%25B8Linked-List-%25EB%258B%25A8%25EC%259D%25BC%25EC%2597%25B0%25EA%25B2%25B0%25EB%25A6%25AC%25EC%258A%25A4%25ED%258A%25B8-%25EC%259D%25B4%25EC%25A4%2591%25EC%2597%25B0%25EA%25B2%25B0%25EB%25A6%25AC%25EC%258A%25A4%25ED%258A%25B8&psig=AOvVaw3eTuzLqxuMjPKs_v5QHkNU&ust=1711852710285000&source=images&cd=vfe&opi=89978449&ved=0CBIQjRxqFwoTCKi8wbn6moUDFQAAAAAdAAAAABAE

 

양방향으로 향하는 노드가 있기때문에 이전 노드도 탐색이 유리하다.

값을 삭제할 때, 양쪽에서 두 개의 노드가 있기때문에 훨씬 간단하다.

하지만 두 개의 노드를 가지고 있는만큼 자료구조의 크기가 약간 더 크다는 단점이 있다.

 

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

https://www.google.com/url?sa=i&url=https%3A%2F%2Fcodingsalon.tistory.com%2F44&psig=AOvVaw3BbEYugHZMVX-ByXahy47w&ust=1711852847131000&source=images&cd=vfe&opi=89978449&ved=0CBIQjRxqFwoTCJiUlfv6moUDFQAAAAAdAAAAABAE

 

 

기본적인 단일 연결리스트는 마지막 노드의 값이 NULL인데, 마지막 노드의 link를 첫번째 노드로 연결해준 형식이다.

 

 

다음 게시물에서는 기본 단일 연결 리스트를 구현해보겠다.