1. 리스트

프로그램을 짜다보면 배열을 사용할 때가 많아진다.

배열은 크기가 한정되어 있기 때문에 공간이 모자라는 경우가 종종 생길 수 있는데, C++을 사용하는 사람들은 STL의 vector를 보통 떠올린다. 나의 경우도 그랬고

하지만 STL의 vector 경우 크기에 상관없이 자유자재로 늘어나는 것처럼 보이지만 배열 형태에서 배열이 가득 찰 때마다 크기를 1.5배 ~ 2배 (컴파일러에 따라 다름) 늘린 후 다시 옮겨담는 형식이라고 한다.

따라서 링크드 리스트랑은 다른 개념이다.

링크드 리스트는 C에서 배열의 크기가 한정되어 있는 한계를 극복하고자 만든 개념이다.

하지만 여러가지 장단점이 있기에 소개하려고 한다.

 

🔹01. 링크드 리스트

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데, 링크드 리스트는 이 중에서 가장 간단히 구현하는 방법이다.

'리스트' 내의 각 요소는 '노드(Node)' 라고 부른다.

'링크드'는 '연결된' 이라는 뜻이다. 즉 링크드 리스트는 연결된 리스트이다.

 

구조

노드의 구조

노드는 데이터와 포인터를 가진 구조입니다.

포인터는 뒤에올 노드를 가르킴으로써 해당 포인터를 이용해 다음 노드를 탐색할 수 있다.

링크드 리스트 구조

첫 번째 노드를 헤드, 마지막 노드를 테일이라고 부른다.

마치 KTX 기차를 이어붙이는 것 처럼 뒤를 이어서 붙인다.

기차 사이의 이음새 역활을 하는 고리가 노드의 포인터가 하는 역할이다.

 

struct Node
{
    Data data;		//데이터
    struct Node* NextNode;	//다음 노드를 가리키는 포인터
}

링크드 리스트를 설정하기 위해서는 코드블록이 종료됨에 따라 사라지지 않도록 malloc() 함수를 통해 할당을 해준다.

이러한 링크드 리스트는 탐색 연산에서 약점을 가지고 있다.

앞에서부터 쭈욱 연결된 구조이다 보니 HEAD부터 탐색을 시작해서 만약 10개의 노드 중 10번째 노드를 찾으려고 한다면 1번부터 탐색해서 10번까지 다달아야한다.

따라서 n개의 노드 중 n번째 노드를 찾으려고 한다면 n번 탐색을 진행해야하기에 비용이 크고 속도가 느리다.

 

❗배열에 비해 링크드 리스트의 장단점 정리❗

🔸단점🔸

  1. 포인터 때문에 각 노드마다 4 byte의 메모리가 추가로 필요함

  2. 최약의 경우 n회의 노드 탐색 루프 -> 비용이 크고 속도가 느림

🔸장점🔸

  1. 새로운 노드의 추가,삽입,삭제가 쉽고 빠름

 

따라서, 링크드 리스트는 추가,삽입,삭제가 잦고 조회는 드문 곳에 유용하다.

 

🔹02. 더블 링크드 리스트

더블 링크드 리스트는 링크드 리스트의 탐색 기능을 개선한 자료구조이다.

이전 노드를 참조하는 포인터를 하나 더 Node 안에 만들어서 양방향 탐색이 가능하도록 만들었다.

🔹03. 환형 링크드 리스트

환형 링크드 리스트는 헤드와 테일을 연결한 링크드 리스트이다.

이러한 방법을 사용하면 테일에 접근하는 비용이 작아져서, 뒤에서부터 노드를 찾아 나가는 탐색을 구현할 수 있다.

예를들어 10개의 노드 중 8번째를 찾고 싶다면 HEAD에서 TAIL로 2번 탐색하면 더 빠르게 찾을 수 있다.

 

 

🔅알아두면 좋은 TIP🔅

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데,

C++ STL vector도 리스트의 일종이라고 볼 수 있겠다.

여기서 C++ STL vector 는 동적 배열의 형태이고,

C++ STL list는 더블 링크드 리스트로 구성되어있다고 한다.