C언어 연결 리스트

1. 연결된 표현

 

배열을 이용한 구현은 간단하지만 용량이 고정된다는 단점이 있다.

 

Linked represetation(연결된 표현)을 사용하면 용량 변환이 자유롭다.

 

연결된 표현은 데이터와 링크로 구성되어 있고 링크가 노드들을 연결하는 역할을 한다.

 

스택, 큐, 리스트, 덱, 트리, 그래프 등 여러 가지의 자료구조를 구현하는데 사용된다.

 

그림으로 표현하면 다음과 같다.

 

연결된 표현의 특징은 4가지가 있다.

(1) 데이터를 한군데 모아두는 것을 포기한다.

>용량의 변환이 자유롭다는 장점을 가지기 위해서 데이터가 흩어져 있고 링크로 서로를 연결하는 형태인 듯?

(2) 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.

>1번에서 말한 것과 동일.

(3) 순서를 유지하기 위해 각각의 데이터는 ㅇ다음 데이터를 가리키는 줄을 가진다.

>링크를 말하는 거 같다. 다음 노드의 주소가 어디인지를 링크가 가지고 있다는 뜻인 듯.

(4) 첫 데이터에서부터 순서대로 줄을 따라가면 모든 데이터를 방문할 수 있다.

>예상대로다

 

이와 같이 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked list)라고 한다.

> ?? 연결된 표현이랑 다른게 뭔지 모르겠다. 연결 리스트는 연결된 표현의 부분집합인 것 같은데.. 뭐 나중에 알게 되겠지..?

 

 

2. 연결리스트

앞서 말했던 것과 똑같이 연결리스트의 노드는 데이터필드와 링크필드로 나뉘어지고 이 데이터필드는 정수가 될 수도 있고 구조체 같은 자료형이 될 수도 있다. 링크 필드에는 다른 노드를 가리키는, 즉 다른 노드의 주솔르 젖아하는 포인터 변수가 있다. 이 포인터를 이용하여 현재 노드에 연결된 다음 노드를 알수 있다.

 

헤드포인터

연결 리스트는 첫 번째 노드를 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근할 수 있다. 따라서  첫 번째 노드의 주소가 중요한데, 이를 헤드포인터라고 한다. 마지막 노드는 더 이상 연결할 노드가 없는데, 링크 필드의 값을 NULL로 설정하여 이 노드가 마지막임을 표현한다.

 

연결 리스트의 특징

1. 노드들은 메모리 어딘가에 흩어져 있으므로 노드들의 주소가 연결리스트의 순서와 동일하지 않다.

2. 링크 필드를 위한 추가 공간이 필요하다.

3. 연산의 구현이나 사용 방법이 배열에 비해 복잡하다. 이는 오류와 관련이 있다.

4. 오류가 없더라도 동적 할당과 해제가 너무 빈번하게 일어나면 메모리 관리를 위한 처리시간이 길어져 프로그램이 느려질 수 있다.

5. 연속적인 기억공간이 없어도 데이터를 저장하는 것이 간으하고 미리 공간을 확보할 필요도 없다.

 

연결리스트의 종류

1. 단순 연결 리스트(singly linked list)

geeksforgeeks.org

하나의 방향으로 연결되어 있으며, 맨 마지막 노드의 링크 필드는 NULL값을 가진다.

 

2. 원형 연결 리스트

studytonight.com

원형 연결 리스트는 단순 연결 리스트와 같지만 맨 마지막 노드의 링크 값이 다시 첫 번째 노드를 가리킨다는 것이 다르다.

 

3. 이중 연결 리스트(doubly linked list)

geeksforgeeks.org

이중 연결 리스트는 각 노드마다 링크 필드, 즉 포인터가 2개씩 존재한다. 따라서 각각의 노드는 선행 노드(previous node)와 후속 노드(next node)를 모두 가리킬 수 있다.