[자료구조] 리스트

단순 연결 리스트

• 리스트의 항목들을 노드(node)라고 함
• 노드는 데이터 필드와 링크 필드로 구성
• 데이터 필드 : 리스트의 원소, 값을 저장하는 곳
• 링크 필드 : 다른 노드의 주소 값을 저장하는 곳 ( 포인터 )
• 마지막 노드의 링크 값은 NULL
• 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 변수

연결 리스트의 장점

• 삽입, 삭제가 용이
• 연속된 공간 필요 X
• 크기 제한 X ( 배열의 경우 크기 제한이 있음 )

연결 리스트의 단점

• 구현이 어려움
• 오류 발생률이 높음

노드 ( 구조체로 정의 )

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode {

	element data; // 데이터 필드
	struct ListNode* link; // 링크 필드 (포인터 사용)
} ListNode;

int main(void)
{
    //ListNode* p1, p2; 로 만들수 없더라.. p2가 포인터가아닌 구조체로만 만들어짐..
	ListNode* p1, *p2; 

	p1 = (ListNode*)malloc(sizeof(ListNode));
	p1->data = 100;
	p1->link = NULL;

	p2 = (ListNode*)malloc(sizeof(ListNode));
	p2->data = 200;
	p2->link = p1; // p2의 링크 필드에 p1를 가리키게 함
    
    // p2의 링크의 데이터값 출력
	printf("%d", p2->link->data);
}

 

출력 결과

 

노드 생성 함수

ListNode* create_node(element data, ListNode* link)
{
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));

	// malloc 사용 실패시 NULL을 반환하니깐
	if (new_node == NULL)
		printf("메모리 초과 에러");
	
	new_node->data = data;
	new_node->link = link;

	return new_node;
}

create_node 함수에 data와 link를 넘겨준다.

새로 만들 노드의 데이터 필드에 data 값이 들어가고

이 새로운 노드의 링크에는 link가 연결될 것이다.

 

삽입 함수

삽입 함수의 프로토 타입

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node)

• phead : 헤드 포인터 head에 대한 포인터 
• p : 삽입될 위치의 선행 노드를 가리키는 포인터, 이 노드(p)의 다음에 삽입된다. 
• new_node : 새로운 노드를 가리키는 포인터

삽입의 경우를 따져보자

1. head가 NULL인 경우

• 리스트에 아무것도 없다는 것이니 공백 리스트에 삽입이다.
• head가 NULL이니 현재 삽입하려는 노드가 첫 번째 노드가 된다.
• 따라서 head의 값만 변경하면 된다.

2. p가 NULL인 경우

• 리스트의 맨 앞의 노드는 선행 노드가 없으므로, 리스트의 맨 처음에 삽입
• 새로운 노드를 리스트의 맨 앞에 삽입한다.

3. 일반적인 경우 ( head가 null이 아니고 p가 null이 아닌 경우 )

• 리스트의 중간에 삽입 (맨 뒤에 삽입 또한 포함)
• new_node의 link에 p->link값을 넣고, p->link에 new_node를 담아준다.
• 즉, new_node의 링크를 p의 링크로, p의 링크를 new_node로 변경이다.

노드의 중간 삽입

노드의 맨끝 삽입 또한 문제 없음

삽입 함수

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node)
{
	// phead : 헤드 포인터 head에 대한 포인터
	// p : 삽입될 위치의 선행 노드를 가리키는 포인터, 이 노드(p)의 다음에 삽입된다.
	// new_node : 새로운 노드를 가리키는 포인터

	/*
	1. head가 NULL인 경우: 리스트에 아무것도 없다는것이니 공백 리스트에 삽입
	2. p가 NULL인 경우: 리스트의 맨 앞의 노드는 선행 노드가 없으므로, 리스트의 맨 처음에 삽입
	3. 일반적인 경우: 리스트의 중간에 삽입 (맨 뒤에 삽입 또한 포함) 
	*/
	if (*phead == NULL)
		*phead = new_node;
	else if (p == NULL)
	{
		new_node->link = *phead;
		*phead = new_node;
	}
	else
	{
		new_node->link = p->link; // (1)
		p->link = new_node; // (2)
	}


}

 

방문 함수

(1) iteration 버전 ( 반복 버전 )

void display(ListNode* head)
{
	// head를 수정할게 아니라서 그냥 *로 받음(더블이아님, 방문만 할거니)
	ListNode* p = head;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->link;
	}
	printf("\n");
}

(2) recursion 버전 ( 순환 함수 사용 )

void display_recursion(ListNode* head)
{
	ListNode* p = head;
	if (p != NULL)
	{
		printf("%d->", p->data);
		display_recursion(p->link);
	}
}

 

삭제 함수

• p가 NULL인 경우 : 맨 첫 노드의 삭제를 의미한다. ( 헤드 포인터 변경이 필요해짐 )
• p가 NULL이 아닌 경우 : removed의 선행 노드의 p의 링크를 removed의 link로 바꿔주자 

void remove_node(ListNode** phead, ListNode* p, ListNode* removed)
{ /* 
  phead : 헤드 포인터 head의 포인터 
  p : 삭제될 노드의 선행 노드를 가리키는 포인터
  removed : 삭제될 노드를 가리키는 포인터
  */
	if (p == NULL)
		*phead = removed->link; // *phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}

 

합병 코드

ListNode* concat(ListNode* head1, ListNode* head2)
{
	ListNode* p;
	if (head1 == NULL)
		return head2;
	else if (head2 == NULL)
		return head1; // 둘중 하나가 NULL이면 다른 하나 자체가 List임
	else
	{
		p = head1;
		while (p->link != NULL)
			p = p->link;
		p->link = head2;
		return head1;
	}
}

 

head1의 끝을 head2로 연결시키는 함수이다.

 

역순으로 변경 함수

ListNode* reverse(ListNode* head)
{
	// trail : 역순으로 된 리스트
	// middle : 역순으로 만들 노드
	// lead : 역순으로 만들 리스트
	ListNode* trail, *middle, *lead;
	lead = head;
	middle = NULL;
	while (lead != NULL)
	{
		trail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = trail;
	}
	return middle;
}

주석 설명보단

그냥 trail은 흔적, middle은 중간, lead는 선두라고 생각하고 코드의 흐름을 이해하는 게 낫다.

첫 줄의 lead가 있고 노드 4개가 있는 그림은 while문을 들어가기 전 lead를 head로 초기화한 모습이다

그 이후로 각 줄은 while문을 1번 실행시킬 때마다 결과를 나타낸 그림이다.

결국 L은 끝으로 가 null을 가리키게 되고 m이 마지막 노드를 가리키게 된다.

다 돌고 return으로 middle을 해주자 

 

원하는 노드 탐색 함수

ListNode* search(ListNode* head, int x)
{
	ListNode* p;
	p = head;
	while (p != NULL)
	{
		if (p->data == x)
			return p;
		p = p->link;
	}
	return p;
}

head 포인터를 가지고 쭉 노드들을 탐색하며 원하는 값(x)을 찾았으면

현재 p를 반환한다.

 

모든 함수를 사용해보자

main 함수

int main(void)
{
	ListNode* list1=NULL, *list2=NULL;
	ListNode* p=NULL;
	insert_node(&list1, NULL, create_node(10, NULL));
	insert_node(&list1, NULL, create_node(20, NULL));
	insert_node(&list1, NULL, create_node(30, NULL));
	display(list1);
	// 30->20->10

	remove_node(&list1, NULL, list1);
	display(list1);
	// 20->10

	insert_node(&list2, NULL, create_node(60, NULL));
	insert_node(&list2, NULL, create_node(70, NULL));
	insert_node(&list2, NULL, create_node(80, NULL));
	display(list2);
	// 80->70->60


	list1 = concat(list1, list2); // list1의 마지막 노드의 링크를 list2의 헤드 포인터로
	display(list1);
	// 20->10->80->70->60

	list1 = reverse(list1);
	display(list1);
	// 60->70->80->10->20

	p = search(list1, 10);
	if (p != NULL)
		printf("search result:%d", p->data);

}

 

이제 원형 리스트를 생각해본다...

이제부터 plast로 맨 마지막 노드를 가리킬 거고

plast의 다음 노드는 첫 노드이다.

 

원형에서 맨 앞에 노드를 삽입해보자

void insert_first(ListNode** plast, ListNode* new_node)
{
	if (*plast == NULL)
	{
		*plast = new_node;
		new_node->link = new_node;
	}
	else
	{
		new_node->link = (*plast)->link; // (1)
		(*plast)->link = new_node; // (2)
	}

}

 

 

원형 리스트에서 맨 마지막 노드로 삽입해보자

void insert_last(ListNode** plast, ListNode* new_node) {
	if (*plast == NULL)
	{
		*plast = new_node;
		new_node->link = new_node;
	}
	else
	{
		new_node->link = (*plast)->link; //(1)
		(*plast)->link = new_node; //(2)
		*plast = new_node; //(3)
	}
}

 

헤드 노드

• 데이터를 갖지 않고 삽입, 삭제 코드를 간단하게 할 목적으로 만든 노드
• 삽입 및 삭제 시, 헤드 포인터의 NULL 여부 상관없이 구현 가능해짐
• 공백상태에서는 헤드 노드만 존재

이중 연결 리스트의 노드 구조

typedef struct DlistNode {
	element data;
	struct DlistNode* llink;
	struct DlistNode* rlink;

}DlistNode;

 

이중연결 리스트에서 삽입 연산

// new_node를 before 노드의 오른쪽에 삽입
void dinsert_node(DlistNode* before, DlistNode* new_node)
{
	new_node->llink = before;
	new_node->rlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node;

}

 

삭제 함수

(헤드 노드 사용..)

void dremove_node(DlistNode* phead_node, DlistNode* removed)
{
	if (phead_node == removed) //empty list
		return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);

}​