연결 리스트 (Linked List)

연결 리스트 (Linked List)

리스트는 동일한 자료형으로 된 원소들의 모임으로 선형 리스트 (Linear List)와 연결 리스트 (Linked List)로 나뉜다. 선형 리스트는 배열로 구현되는 순서 리스트로 원소들이 메모리에 연속적으로 저장되고 인덱스를 통하여 접근한다. 

반면, 연결 리스트의 원소들은 프로그램 실행 중에 동적으로 생성되거나 삭제되므로 리스트의 크기를 미리 예측할 필요가 없다. 연결 리스트의 원소들은 링크를 통해 서로 연결되어 있기 때문에 논리적으로는 선형적이지만 물리적으로는 분산되어 있다. 연결 리스트는 사용자가 직접 연결 리스트의 노드를 실행 중에 관리해 주어야 하고 이것을 동적 메모리 관리(Dtnamic Memory Management) 라고 한다.

연결 리스트의 원소는 노드(Node)라고 부르며 구조체로 선언되고 정보를 저장하는 데이터 필드와 노드를 연결하는 링크 포인터 필드로 구성된다. 연결 리스트의 노드는 링크 포인터가 자신과 동일한 구조체 자료형을 참조하기 때문에 자기 참조형 구조체 (Self-Referential Structure) 라고도 부른다.

 

ex) 연결 리스트 노드의 구조

data

link

 

---

 

정적 메모리 공간에 연결 리스트를 생성하는 프로그램

3개의 노드가 링크로 연결된 연결 리스트를 생성하는 프로그램이다. 각 노드의 데이터 필드에는 소수가 크기 순서대로 저장된다. 연결 리스트 노드는 node_type 구조체형으로 선언되고, 링크 포인터는 이 구조체에 대한 포인터이므로 node_ptr로 선언된다.

// 정적 메모리 공간에 3개의 노드로 연결 리스트를 생성한다

#include <stdio.h>
typedef struct node_type* node_ptr;
struct node_type
{
	int data;
	node_ptr link;
};

void main()
{
	struct node_type node1, node2, node3;
	node1.data = 7;
	node2.data = 11;
	node3.data = 13;
	node1.link = &node2;
	node2.link = &node3;
	node3.link = NULL;
	printf("%d %d %d", node1.data, node2.data, node3.data);
}

 

---

 

연결 리스트의 노드를 위한 공간을 요청하는 명령문

연결 리스트의 노드를 위한 공간을 요청할 때는 구조체 자료형의 크기를 malloc 함수에 전달해 준다. node_type과 node_ptr은 각각 구조체형과 구조체 포인터형으로 선언되었다고 가정한다.

ex) node1 = ( node_ptr ) malloc ( sizeof( struct node_type ) );

 

연결 리스트 노드의 멤버에 접근하는 방법

ex) node1 -> data

 

동적 메모리 할당으로 연결 리스트를 생성하고 삭제하는 프로그램

// 동적 메모리 할당으로 연결 리스트를 생성하고 삭제하는 예제

#include <stdio.h>
#include <stdlib.h>
typedef struct node_type* node_ptr;
struct node_type
{
	int data;
	node_ptr link;
};

void main()
{
	node_ptr node1, node2, node3;
	node1 = (node_ptr)malloc(sizeof(struct node_type));
	node2 = (node_ptr)malloc(sizeof(struct node_type));
	node3 = (node_ptr)malloc(sizeof(struct node_type));
	node1->data = 7;
	node2->data = 11;
	node3->data = 13;
	node1->link = node2;
	node2->link = node3;
	node3->link = NULL;
	printf("node1 : %d ", node1->data);
	printf("node2 : %d ", node2->data);
	printf("node3 : %d \n", node3->data);
	free(node1);
	free(node2);
	free(node3);
}

 

---

 

허상 참조 (Dangling Reference)

malloc 함수에 의해 할당된 공간에 대한 포인터 변수는 그 공간에 접근할 수 있는 유일한 수단이다. 따라서 이 포인터의 값이 변경된다면 그 공간에 대한 접근이 불가능해지며 결과적으로 할당된 공간이 방치되는 허상 참조 (Dangling Reference) 상황을 초래하게 된다.

ex) ptr = ( int * ) malloc ( sizeof ( int ) );

ptr2 = ( int * ) malloc ( sizeof ( int ) );

ptr1 = ptr2;

 

---

 

단방향 연결 리스트 (Singly Linked List)

연결 리스트의 노드들이 한쪽 방향으로만 연결된 경우를 단방향 연결 리스트 (Singly Linked List) 라고 한다. 첫 번째 노드를 참조하는 포인트를 리스트 포인터 (List Pointer) 라고 하고 이를 통하여 리스트 노드들을 탐색한다.

 

---

 

연결 리스트에 노드를 삽입하는 알고리즘

1. malloc 함수로 삽입할 노드를 생성하고 그 주소를 포인터 node에 할당한다.

2. 생성된 노드의 data 필드에 값을 저장하고, link 필드에 NULL을 저장한다.

3. 연결 리스트 포인터가 list이라고 가정할 때,

1. 연결 리스트가 비어있는 경우(empty)
   1. 삽입할 노드가 유일한 노드이므로 이 노드가 첫 노드가 되도록 리스트 포인터에 노드의 주소 값을 저장하고 종료한다.
2. 연결 리스트가 비어있지 않은 경우(not empty)
   1. 연결 리스트의 중간에 삽입되는 경우
      1. 앞 노드의 링크 필드 값을 node의 link에 저장한다.
      2. 앞 노드의 링크 필드에 노드의 주소 값을 저장하고 종료한다.
   2. 연결 리스트의 맨 앞에 삽입되는 경우
      1. 삽입할 노드의 링크 필드에 연결 리스트 포인터 값을 저장한다.
      2. 연결 리스트 포인터가 노드를 가리키도록 하고 종료한다.

 

연결 리스트의 노드 삽입 프로그램

// 연결 리스트의 노드 삽입 프로그램

#include <stdio.h>
#include <stdlib.h>
typedef struct node_type* node_ptr;
struct node_type
{
	int data;
	node_ptr link;
};
node_ptr list;

void insert_node(node_ptr prev, int data);
void print_list(node_ptr list);

void main()
{
	node_ptr node1, node2, node3;
	node1 = (node_ptr)malloc(sizeof(struct node_type));
	node1->data = 100;
	node1->link = NULL;
	list = node1;
	node2 = (node_ptr)malloc(sizeof(struct node_type));
	node2->data = 200;
	node2->link = NULL;
	node1->link = node2;
	print_list(list);
	insert_node(node1, 150);
	print_list(list);
}

void insert_node(node_ptr prev, int data)
{
	node_ptr node;
	node = (node_ptr)malloc(sizeof(struct node_type));
	if (!node) exit(1);
	node->data = data;
	node->link = NULL;
	if (!list)
	{	// 연결 리스트가 비어 있는 경우
		list = node;
	}
	else if (prev)
	{	// 중간에 삽입되는 경우
		node->link = prev->link;
		prev->link = node;
	}
	else
	{	// 맨 앞에 추가되는 경우
		node->link = list;
		list = node;
	}
}

void print_list(node_ptr list)
{
	while (list)
	{
		printf("%d ", list->data);
		list = list->link;
	}
	printf("\n");
}

 

---

 

연결 리스트의 노드 삭제 알고리즘

1. 연결 리스트가 비어있는 경우(empty)
   1. 그대로 종료한다.
2. 연결 리스트에 노드가 존재하는 경우
   1. 연결 리스트의 중간 노드를 삭제하는 경우 : 삭제 노드의 앞 노드의 링크 필드에 삭제할 노드의 링크를 저장한다.
   2. 연결 리스트의 맨 앞 노드를 삭제하는 경우 : 연결 리스트 포인터에 삭제할 노드의 링크를 저장한다.
3. 노드를 삭제하고 종료한다.

 

연결 리스트의 노드 삭제 프로그램

// 리스트의 노드 삭제하기

#include <stdio.h>
#include <stdlib.h>
typedef struct node_type* node_ptr;
struct node_type
{
	int data;
	node_ptr link;
};
node_ptr list;

void delete_node(node_ptr prev, node_ptr node);
void print_list(node_ptr list);

void main()
{
	node_ptr node1, node2, node3;
	node1 = (node_ptr)malloc(sizeof(struct node_type));
	node1->data = 100;
	node1->link = NULL;
	list = node1;
	node2 = (node_ptr)malloc(sizeof(struct node_type));
	node2->data = 200;
	node2->link = NULL;
	node1->link = node2;
	node3 = (node_ptr)malloc(sizeof(struct node_type));
	node3->data = 300;
	node3->link = NULL;
	node2->link = node3;
	print_list(list);
	delete_node(node1, node2);	// node1은 이전 노드, node2는 삭제할 노드
	print_list(list);
}

void delete_node(node_ptr prev, node_ptr node)
{
	if (prev)
		// 중간 노드가 삭제되는 경우
		prev->link = node->link;
	else
		// 맨 앞 노드가 삭제되는 경우
		list = node->link;

	free(node);
}

void print_list(node_ptr list)
{
	while (list)
	{
		printf("%d ", list->data);
		list = list->link;
	}

	printf("\n");
}