[ 연결리스트 구조체 ]

프로그래밍에서 빼놓을 수 없는 자료구조인 연결 리스트(linked list)에 대해 구현해보겠다.

연결리스트는 데이터가 담긴 노드(메모리 공간)을 일렬로 연결해놓았다고 해서 연결리스트라고 부르며 특징은 다음과 같다.

• 리스트의 중간 지점에 노드를 손쉽게 추가하거나 삭제할 수 있다.
• 특정 노드를 찾으려면 노드를 모두 검색해야 한다.
• 크기가 고정되어 있지 않다.

다음은 다른 노드를 가리키는 포인터가 하나씩만 있는 **단일 연결 리스트(singly linked list)**이다.

지금부터는 구조체, 포인터, 함수, 메모리 할당을 사용하여 단일 연결리스트를 구현하는 방법을 알아보겠다. 참고로 연결리스트는 기본적인 자료구조 이지만 포인터를 사용하다 보니 많은 사람들이 어려워하는 부분이니 너무 걱정하지 말자!

연결리스트 구조체 만들고 사용하기

먼저 연결리스트의 구조체를 정의해야 한다. 연결리스트는 노드들의 집합이므로 실제로는 노드의 구조체만 정의하면 된다.

struct NODE {// 연결 리스트의 노드 구조체struct NODE *next;// 다음 노드의 주소를 저장할 포인터int data;// 데이터를 저장할 멤버
};

NODE 구조체에서 가장 중요한 부분은 **struct NODE *next**이다. 얼핏 보면 구조체 자기 자신의 포인터를 멤버로 가지고 있는데 전혀 어렵지 않다!

next에는 NODE 구조체로 만든 다른 노드의 메모리 주소를 저장한다. 즉, 자기 자신이 아닌 다른 노드의 메모리 주소를 저장한다는 점을 기억하라.

NODE구조체에서 데이터는 int형 하나만 저장했다. 실제로 사용할 때는 용도에 따라서 다양한 자료형으로 된 멤버 여러개를 넣으면 된다.

이제 단일 연결리스트에서 노드의 종류를 알아볼 것이다. 노드는 역할에 따라서 두 가지로 나뉘어 진다.

• 머리 노드(head node) : 단일 연결리스트의 기준점이며 헤드(head)라고도 불린다. 머리 노드는 첫번째 노드를 가리키는 용도이므로 데이터를 저장하지 않는다.
• 노드(node) : 단일 연결리스트에서 데이터가 저장되는 실제 노드이다.