[C] 연결리스트 : 단순연결리스트

연결리스트를 복습해보자

 

연결된 리스트 형태의 자료구조를 연결리스트라고 한다 (단순)

 

연결리스트는 자기 참조 구조체를 쓸 것이며,

lisert 함수를 생성해 연결리스트에 데이터를 추가할 것이며

delete함수를 생성해 연결리스트의 데이터를 삭제할 것이다.

print_list함수를 따로 생성해 연결리스트에 있는 데이터를 순서대로 출력하기도 할 것이다.

.

.

외에 여러 연산이 있지만 추후 필요하면 기술하기로 하겠다

 

배열과 연결리스트의 장/단점 으로는 무엇이 있을까?

배열은 구현이 간단하고 노드를 찾는 검색 속도가 빠르다.

인덱스를 이용해 해당 위치로 바로 이동할 수 있기 때문이다. 

하지만 동적으로 크기를 변경하는게 힘들다.

+배열의 경우 중간 데이터를 삭제할 때,

해당 데이터 뒤에 있는 데이터를 앞으로 한칸씩 당겨와야 한다는 단점이 있다.

 

연결리스트는 크기가 제한되지 않았지만

head로 부터 출발해서 원하는 위치까지 가야하므로

탐색하는데에 배열보다 시간이 오래 걸린다.

데이터를 삭제할 때는 포인터만 바꾸고,

지우길 원하는 데이터는 동적 할당 해제를 해주면 된다.

배열에 비해 몹시 편리하다.

 

 

---

 

연결리스트에 대한 이야기를 해보자

 

연결리스트는 노드들이 줄(포인터)로 연결되어있는 형태이다.

노드의 줄(link)부분을 따라가면 다음 노드를 만날 수 있다.

 

그렇다면 노드는 무엇인가?

노드는, 데이터와

(다음 노드를 연결해주는-) 포인터를 모아둔 것을 말한다.

 

노드들의 집합을 연결리스트라고 부른다.

노드들은 메모리의 어떤 위치에나 있을 수 있으며

데이터 필드와 링크 필드로 구성되어 있다.

연결리스트 노드의 구조, 참고자료

데이터 필드에는 원하는 데이터를 넣을 수 있다.

링크 필드는 다른 노드를 가리키는 포인터가 저장된다.

 

첫 번째 노드를 알면 포인터를 이용해서 다음 노드로 넘어갈 수 있고,

모든 노드를 탐색할 수 있게 된다.

 

그래서 첫 번째 노드가 중요한데,

첫 번째 노드를 가리키는 변수를 헤드 포인터 라고 한다.

 

마지막 노드의 링크 필드는 NULL로 설정된다.

연결리스트의 3가지 종류, 참고자료

 

연결리스트는 다음과 같은 3가지 종류가 있다.

이번 포스팅에서는 단순연결리스트만 소개할 것이지만 맛보기를 하자면..

 

단순연결리스트 >> 한 방향으로만 연결된 리스트

원형연결리스트 >> 마지막 노드가 첫번째 노드를 가리켜서 순환

이중연결리스트 >> 각 노드마다 2개의 링크가 존재, 링크 하나는 다음 노드를, 다른 하나는 앞의 노드를 가리킴

 

---

 

단순연결리스트에 대해 알아보자

 

단순연결리스트란 한 방향으로만 연결된 리스트이다.

노드의 정의는 자기 참조 구조체를 이용할 것이며,

malloc()을 호출하여 동적으로 메모리를 할당할 것이다.

노드의 삭제는 free()를 호출할 것이다.

 

insert_first, delete_first 함수를 생성해서

간단한 단순연결리스트를 구현해보자

 

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

//노드의 정의
typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;
//자기 참조 구조체 이용 (자기 자신을 참조하는 포인터를 포함하는 구조체)
//data에는 데이터를 저장, link는 포인터를 저장 - 다음 노드의 주소가 저장

//맨 앞에 삽입하는 방법
//1.새로 삽입할 노드 p 생성
//2.p의 링크를 head를 가리키기
//3.head가 p를 가리키도록 변경하고 리턴
ListNode* insert_first(ListNode* head, element data) {
	//1.
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = data;
	//2.
	p->link = head;
	//여기서 바로 return p를 해도 됨
	head = p;
	return head;
}


//맨 앞의 데이터 삭제하기
//1.head의 link가 가리키고 있는 노드, 즉 2번째 노드를 head가 가리키도록 설정 함
//2.첫번째 노드를 free()해줌
ListNode* delete_first(ListNode* head) {
	//지울 첫번째 노드를 removed에 임시 할당
	ListNode* removed;
	//만약 노드가 비어있다면 null값 리턴
	if (head == NULL) return NULL;
	removed = head;
	//1.
	head = removed->link;
	//2.
	free(removed);
	return head;
}


void print_list(ListNode* head) {
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL\n");
}


int main() {
	//공백 리스트 생성
	//비어있는 단순연결리스트를 생성
	//노드는 아직 존재X
	//insert함수를 통해 노드 생성 - malloc()이용
	ListNode* head = NULL;

	//연결리스트의 앞에서 데이터 삽입
	// 10
	// 20 10
	// 30 20 10
	head = insert_first(head, 10);
	head = insert_first(head, 20);
	head = insert_first(head, 30);

	//출력 30 20 10
	print_list(head);

	//맨앞의 노드 삭제
	head = delete_first(head);

	//출력 20 10
	print_list(head);
}

 

출력 결과

 

하지만 단순연결리스트에는 단점이 있다.

삽입과 삭제가 용이하지 않은데,

이러한 단점을 보완한 연결리스트로

원형 연결리스트와 이중 연결리스트가 있다.

다음 포스팅에는 다른 여러 연결리스트에 대해 소개하도록 하겠다 ㅠ ㅠ 

 

정신차리니 8월 중순이구만요...

꾸준히 업로드 하도록 하겠습니다

반성 반성.. 또 반성!

 

 

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음