자료구조 제 9강 (연결리스트-개념과 기본 동작들)

리스트

• 기본적인 연산: 삽입, 삭제, 검색 등
• 리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결리스트

배열의 단점

• 크기가 고정 - reallocation이 필요
• 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 함

연결리스트

• 다른 데이터의 이동없이 중간에 삽입하거나 삭제가 가능함
• 길이의 제한이 없음
• 랜덤 액세스가 불가능

랜덤 액세스: 배열의 시작주소에서 n번째 칸까지 한 번에 갈 수 있는 것과 같음 (ex. 시작주소 + (n * 1칸의 크기))

 

 

연결리스트: 노드들이 link로 서로 연결되어있는 자료구조

노드: 어떤 데이터와 그 다음 데이터의 주소가 하나로 묶여있는 단위

• 각각의 노드는 필요한 데이터 필드와 하나 혹은 그 이상의 링크 필드로 구성
• 링크 필드는 다음 노드의 주소를 저장
• 첫 번째 노드의 주소는 따로 저장해야 함
• 마지막 노드의 next 필드에는 NULL을 저장하여 연결리스트의 끝임을 표시한다.

#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;

	Node* q = (Node*)malloc(sizeof(Node));
	q->data = "Thursday";
	q->next = NULL;
	head->next = q;					//Thursday를 Tuesday의 다음 노드로 만들어줌

	q = (Node*)malloc(sizeof(Node));
	q->data = "Moday";
	q->next = head;
	head = q;					//새로운 연결리스트의 첫번째 노드를 저장

	Node* p = head;
	while (p != NULL) {
		printf("%s\n", p->data);
		p = p->next;				//그 다음 노드의 주소를 p에 저장
	}
}

 

 

 

연결리스트 맨 앞에 새로운 노드 삽입하기

1. 새로운 노드를 만들고 추가할 데이터를 저장한다.
2. 새로운 노드의 next 필드가 현재의 head노드를 가리키도록 한다.
3. 새로운 노드를 새로운 head 노드로 한다.

*head노드가 새로운 노드를 먼저 가리키게 하면, 기존 head노드가 가리키던 노드의 주소를 잃게 된다.

 

 

연결리스트 맨 앞에 새로운 노드 삽입하기

 

→첫번째 노드를 가리키는 포인터 head가 전역변수인 경우

void add_first(char* item)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = item;
	temp->next = head;
	head = temp;
}

 

→첫번째 노드를 가리키는 포인터 head가 전역변수가 아닌 경우

1.

void add_first(Node** ptr_head, char* item)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = item;
	temp->next = *ptr_head;
	*ptr_head = temp;
}

이렇게 구현할 경우 이 함수는 add_first(&head, item_to_store); 과 같이 호출해야 한다.

 

2.

Node* add_first(Node* head, char* item)
{
	Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = item;
    temp->next = head;
    return temp;		//새로운 head노드의 주소를 return한다.
}

이렇게 구현할 경우 이 함수는 head = add_first(head, item_to_store); 과 같이 호출해야 한다.

 

 

 

어떤 노드 뒤에 새로운 노드 삽입하기

1. 새로운 노드를 만들고 데이터를 저장한다.
2. 새로운 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다.
3. 새로운 노드를 prev의 다음 노드로 만든다.

int add_after(Node* prev, char* item)
{
	if (prev == NULL)
		return 0;
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = item;
	tmp->next = prev->next;
	prev->next = tmp;

	return 1;
}

 

첫번째 노드의 삭제

• head가 현재 head노드의 다음 노드를 가리키게 만든다. ( head = head->next; )

Node* remove_first() {
	if (head == NULL) {
		return NULL;
	}
	else {
		Node* tmp = head;
		head = head->next;
		return tmp;
	}
}

*기존 head노드가 필요없다면 free 시킨다.

 

 

어떤 노드의 다음 노드 삭제하기

 

• prev가 가리키는 노드의 다음 노드를 삭제한다.

• prev의 다음 노드가 null이 아니라면 prev의 next 필드가 현재 next 노드의 다음 노드를 가리키게 만든다.

if (prev->next != NULL)
	prev->next = prev->next->next;

Node* remove_after(Node* prev) {
	Node* tmp = prev->next;
	if (tmp == NULL) {
		return NULL;
	}
	else {
		prev->next = tmp->next;
		return tmp;
	}
}

 

*단순연결리스트에 어떤 노드를 삭제할 때는 삭제할 노드의 바로 앞 노드의 주소가 필요하다. 삭제할 노드의 주소만으로는 삭제할 수 없다.

 

 

 

연결리스트 순회하기

• 연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회한다고 함.
• 아래의 함수는 입력된 문자열 word와 동일한 단어를 저장한 노드를 찾아서 그 노드의 주소를 반환함. (연결리스트 순회의 목적)

Node* find(char* word) {
	Node* p = head;
	while (p != NULL) {
		if (strcmp(p->data, word) == 0)
			return p;
		p = p->next;
	}
	return NULL;
}

• 연결리스트의 index번째 노드의 주소를 반환한다.

Node* get_node(int index) {
	if (index < 0)
		return NULL;
	Node* p = head;
	for (int i = 0; i < index && p != NULL; i++)
		p = p->next;
	return p;
}

 

• 연결리스트의 index번째 위치에 새로운 노드를 만들어서 삽입한다.

int add(int index, char* item) {
	if (index < 0)
		return 0;

	if (index == 0) {
		add_first(item);
		return 1;
	}
	Node* prev = get_node(index - 1);
	if (prev != NULL) {
		add_after(prev, item);
		return 1;
	}
	return 0;
}

 

• index번째 노드를 삭제하고, 그 노드에 저장된 데이터를 반환한다.
• remove(int index)

Node* remove(int index) {
	if (index < 0) {
		return NULL;
	}
	if (index == 0) {
		return remove_first();
	}
	Node* prev = get_node(index - 1);
	if (prev == NULL)
		return NULL;
	else {
		return remove_after(prev);
	}
}

 

• 입력된 스트링을 저장한 노드를 찾아 삭제한다.
• 삭제된 노드에 저장된 스트링을 반환한다.
• remove(char* item)

Node* remove(char* item) {
	Node* p = head;
	while (p != NULL && strcmp(p->data, item) != 0)
		p = p->next;
	//삭제할 노드를 찾았음. 하지만 노드를 삭제하기 위해서는
	//삭제할 노드가 아니라 직전의 노드의 주소가 필요함
}

q는 항상 p의 직전 노드를 가리킴. p가 첫번째 노드일 경우 q는 NULL임.

Node* remove(char* item) {
	Node* p = head;
	Node* q = NULL;
	while (p != NULL && strcmp(p->data, item) != 0) {
		q = p;
		p = p->next;
	}
	if (p == NULL)
		return NULL;
	if (q == NULL)
		return remove_first();
	else
		return remove_after(q);
}

 

• 연결리스트에 데이터들이 오름차순으로 정렬되어있다는 가정하에서 새로운 데이터를 삽입한다.

void add_to_ordered_list(char* item) {
	Node* p = head;
	Node* q = NULL;
	while (p != null && strcmp(p->data, item) <= 0) {
		q = p;
		p = p->next;
	}
	if (q == NULL)
		add_first(item);
	else
		add_first(q);
}