(C언어) 연결 리스트(1)(노드의 정의,생성,연결) [자료구조]

 

자료구조에서 매우 중요한 연결 리스트의 기본적인 구조에 대해 알아보자.

연결 리스트는 노드라고 부르는 아이템의 리스트이다. 그중 단일, 원형 연결 리스트는 하나의 링크 필드를 가지는 리스트이고 두개의 링크 필드를 가지는 리스트는 이중 연결 리스트임을 이전에 배웠다.

2022.02.19 - [SW/Data structure] - [자료구조] 리스트(List)

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

연결 리스트의 구성요소는 다음과 같다.

• Head 포인터 : 연결리스트에서 첫 번째 노드의 주소를 가지는 포인터
• 노드 : 연결 리스트의 아이템
• 데이터 필드 : 연결 리스트의 각 노드에 저장된 데이터
• 링크 필드 : 다른 노드의 주소를 저장하는 부분

---

## 노드의 정의

먼저 노드의 구조를 살펴보면 값을 저장하는 데이터 필드, 해당 노드와 연결된 다음 노드의 주소를 저장하는 포인터인 링크 필드가 있다.

노드 구조

typedef int element;
typedef struct{
	element data; // 노드의 데이터를 담고 있는 데이터 필드
	struct ListNode *link; // 다른 노드를 가리키는 링크 필드
}ListNode;

자기 참조 구조체를 이용하여 링크 필드를 구현하였다. 데이터 필드의 값들은 정수 같은 가본 자료형이나 구조체 같은 자료형이 될 수 있다. 구조체를 통해 노드를 정의했지만 아직 노드는 생성되지 않은 상태이다. 노드를 생성하기 위해서는 구조체 ListNode를 선언해야 한다.

---

## 노드의 생성

일반적으로 연결 리스트에서 필요한 노드를 생성할때 동적 메모리 할당을 통해 노드를 생성한다. 자세한 이유는 리스트의 장점을 활용하기 위해서이다. 크기가 정해져 있어 메모리 낭비가 심한 배열과는 달리 리스트의 경우 필요한 만큼만 메모리를 사용할 수 있는 장점을 활용하기 위해 동적 메모리 할당을 사용한다. malloc() 함수를 이용하여 노드 크기만큼의 동적 메모리를 할당받아 헤드 포인터에 저장해보겠다.

ListNode *Head = (ListNode *)malloc(sizeof(ListNode)); // 헤드 포인터에 동적 메모리의 주소 저장

노드 생성

 현재 노드를 동적으로 생성한 상황이다. 헤드포인터는 생성한 노드를 가리키고 있다. 하지만 아직 노드의 데이터 필드, 링크 필드에는 아무것도 채워지지 않은 상태이다. 그럼 각 필드에 값을 저장해보자.

Head->data = 1;
Head->link = NULL;

각 필드에 값 저장

코드데로 값을 저장했을 때의 상황이다. 흔히 연결 리스트에서 마지막 노드를 나타낼 때 마지막 노드의 링크 필드를 NULL값으로 저장한다. 그렇게 함으로써 리스트의 끝을 쉽게 할 수 있으며 뒤에서 나오는 리스트를 순차적으로 탐색하는데 NULL값을 활용해 반복문을 사용할 수 있다. 현재 상황과는 다른 이야기지만 리스트가 만약 공백이라면 헤드 포인터의 값이 NULL인지 검사해보면 된다. 어떠한 노드도 없으므로 헤드 포인터의 값은 NULL이 될 것 이기 때문이다.

---

## 노드의 연결

연결 리스트는 여러 개의 노드를 서로 연결 할 수 있다. 그 방식에 대해 자세히 알아보자. 이전에 생성했던 해드 포인터 노드와 새로운 노드가 있다 두 노드를 어떻게 연결할 수 있을까?

서로 다른 노드

방법은 간단하다. 노드간의 순서에 따라 다르겠지만 예시로는 그림대로 첫 번째 노드 뒤에 두 번째 노드를 연결해보겠다. 그렇게 하기 위해서는 링크 필드를 통해 두 번째 노드를 가리키도록 하면 된다. 즉 Head->link에 L을 저장하면 된다.

ListNode *Head = malloc(sizeof(ListNode));
Head->data = 1;
Head->data = NULL; // 첫번째 노드 생성 및 값 저장

ListNode *L = malloc(sizeof(ListNode));
L->data = 10;
L->data = NULL; // 두번째 노드 생성 및 값 저장

Head->link = L;

두 노드의 연결

두 노드가 연결되었다. 이 방법을 통해 연결 리스트에서 노드의 삽입과 삭제 같은 기본적인 연산을 할 수 있다. 다음에는 단일 연결 리스트에서 기본적인 연산을 알아보자.

(C언어) 연결 리스트(2)(삽입, 삭제 연산) [자료구조]

(C언어) 연결 리스트(2)(삽입, 삭제 연산) [자료구조]