[C언어] 연결리스트 - 개념과 기본 동작들(1)

배열은 각각의 항목들이 메모리의 연속된 공간에 연속되게 저장되어 있는 구조를 말합니다. 각 항목들은 메모리상에 자신들의 주소를 가지고 있기 때문에, 그 인덱스 번호만 알고 있다면 어느 데이터에서나 접근이 가능한 random access가 가능합니다.

 

반면 연결 리스트는 메모리에 연속되게 저장되지 않고, 대신 다음 데이터가 저장된 공간이 두 번째 주소에 저장되어 있고, 두 번째 주소의 값은 세 번째 값의 주소를 가지고 있고,  그렇게 연결을 하다 마지막 데이터는 다음 데이터의 주소를 null 데이터 저장하는 구조입니다. 메모리상에서의 순서가 중요하지 않습니다. 하지만 배열과 달리 random access가 불가능합니다.

연결 리스트는 메모리 상의 순서가 상관이 없습니다. 때문에 연결된 리스트에서 데이터를 삭제하거나, 중간에 삽일할 때 배열처럼 새로운 데이터가 들어갈 자리를 비워주느라 특정 인덱스부터의 데이터를 뒤로 미루거나 앞당길 필요가 없습니다.

연결 리스트는 위의 그림과 같이 하나의 데이터 필드와, 하나의 링크 필드로 구성되어 있습니다. 데이터 필드에는 자신이 저장하려는 하나 이상의 데이터 변수들을 저장하고, 링크 필드에는 자신과 연결되는 다음 노드의 주소를 저장함.

연결 리스트를 사용하면서 새롭게 추가되는 중간 노드들의 주소를 숙지할 필요는 없습니다. 다만 첫 번째 노드의 주소는 연결 리스트를 호출하고 사용하는 매개이기 때문에 반드시 변수에 따로 저장해야 합니다.

#include <stdio.h>
#include <stdlib.h>
struct node
{
	char* data; // 데이터 영역
	struct node* next; // 자기 참조형 구조체
} ;

typedef struct node Node;
Node* head = NULL;

// 연결 리스트는 배열처럼 미리 메모리를 확보하고 만드는 방식이 아님
// 데이터가 필요할 때마다 노드를 추가

int main()
{
	head = (Node*)malloc(sizeof(Node)); // 첫 번째 노드의 시작 주소 할당
	head->data = "Tuesday";
	head->next = NULL; // 현재까지는 마지막 주소이기 때문에 next에 NULL 저장

	Node* q = (Node*)malloc(sizeof(Node));
	q->data = "Thursday";
	q->next = NULL;	// 이제 q가 마지막 노드
	head->next = q;	// head 노드 뒤에 q 노드를 연결


	q = (Node*)malloc(sizeof(Node)); // 포인터 q를 재활용
	q->data = "Monday";
	q->next = head;	// Monday가 첫 번째 노드
	head = q;	// 첫번째 노드의 시작 주소를 q로 옮김

	Node* p = head;		// 출력하려는 노드의 첫번째 주소. head를 그대로 쓰면 head가 결국 NULL이 됨
	while (p != NULL)	// 노드에 저장된 데이터를 순서대로 출력
	{
		printf("%s\n", p->data);
		p = p->next;	// 다음 노드로 넘어감
	}
}

---

	Node* tmp = (Node*)malloc(sizeof(Node));	// 새로운 노드를 생성
	tmp->data = "Sunday";	// 새로운 데이터 생성
	tmp->next = head;		// 연결할 주소를 next에 저장
	head = tmp;

연결 리스트의 맨 앞에 새로운 노드를 추가할 때 주의해야 할 점은, 과연 이렇게 새로운 노드를 추가하는 방식이 모든 상황에서도 동작하는지를 파악하는 것입니다.

만약 기존의 연결 리스트의 길이가 0일 경우, 즉 head에 데이터가 저장되어있지 않고 NULL인 경우에도 정상적으로 프로그램이 동작하는지 확인해야 합니다.

 

1.

void add_first(char* item, Node **ptr_head)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = *ptr_head; // 주소를 de-referencing해서 
	*ptr_head = tmp;
}

 

2.

Node* add_first2(char* item, Node* HEAD)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = HEAD; 
	return tmp; // 새로운 노드의 주소를 리턴
}

int main()
{
.
.
	head = add_first2(head)
.
.

함수로 연결 리스트의 맨 처음에 노드를 추가할 때는 모두 동적 할당을 통해 노드를 생성합니다. 동적 할당을 통해 생성된 노드 heap 영역에 저장되기 때문에 함수가 종료되더라도 메모리에서 사라지지 않습니다. 다만 주의해야 할 점은, 함수의 인자로 전달되는 main 영역의 head, 즉 연결 리스트의 첫 번째 주소는 call by value로 복사되어 함수 내에서 사용이 됩니다. 때문에 head를 직접 가져오지 않고, head의 포인터를 가져와 포인터를 dereference 하여 새로운 노드의 next에 사용하는 방법 1과, 아니면 함수의 리턴 타입을 Node 구조체의 포인터로 지정하여 main 함수에서 head의 값을 리턴 받은 새로운 노드의 시작 주소로 변경하는 방법 2 이렇게 두 가지가 존재합니다.