연결리스트 기본 개념

• List (리스트) 는 순서가 의미가 있다.

(1, 2, 3) != (3, 2, 1)

 

• Set (집합) 은 순서가 무의미하다.

{1, 2, 3} == {3, 2, 1}

 

 

리스트를 구현하는 대표적인 두 가지 방법은 배열, 연결리스트 이다.

 

 

 

배열은 앞서 전화번호부를 만들때 배웠으며, 단점은 배열은 크기가 고정되어 있다는 것이다.

따라서 reallocation(재할당) 이 필요했었다.

또한 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 하는 단점이 있었다.

 

vs

 

그러나 연결리스트는 다른 데이터의 이동 없이 중간에 삽입하거나 삭제가 가능하며, 길이 제한이 없다.

하지만 랜덤 엑세스가 불가능하다는 단점이 있다.

 

 

 

 

배열과 연결리스트의 저장방식 차이

 

배열과 연결리스트의 메모리를 살펴보자.

배열은 데이터들이 연속된 공간에 저장되는 것을 볼 수 있다. 따라서 목요일을 삽입하려면 화요일과 금요일 사이에 삽입되어야 한다. 

그러나 연결리스트는 반드시 순서대로 저장될 필요가 없으며 대신 다음 주소를 가리키는 메모리의 번지가 저장될 한 칸이 더 필요하다.

 

 

 

 

목요일 삽입하는 경우

 

즉, 목요일을 삽입하는 경우 배열과 달리 아무데나 삽입할 수 있다. 여기에선 108번지에 삽입을 해주었다.

 

 

 

 

 

노드

각각의 노드는 필요한 데이터 필드와 하나 혹은 그 이상의 링크 필드로 구성되어 있다. 링크 필드는 다음 노드의 주소를 저장한다. 여기에서 기억해야 할 점은 첫번째 노드의 주소이다. 

첫번째 노드의 주소는 따로 저장해야 하며, 절대 잊어버려서는 안된다.

 

 

첫번째 노드의 주소는 head 가 반드시 기억하고 있다.

 

 

 

 

노드는 구조체이다. 앞에서 보았듯이 두개 이상의 필드를 저장해야 하기 때문이다.

각 노드에 저장될 데이터는 하나의 문자열이라고 가정하자.

 

struct node {
	char *data;   // 데이터는 문자열이라고 가정
    	struct node *next;   
}

tydedef struct node Node;
Node *head = NULL;   // 연결리스트의 첫번째 노드의 주소를 저장할 포인터 생성

 

 

 

 

 

다음은 main 함수이다. 먼저 첫번째 노드를 생성해보자.

 

int main()
{
 Node *head = (Node *)malloc(sizeof(Node));   // head 포인터 변수 생성
 head->data = "Tuesday";
 head->next = NULL;
 
 ...

 

첫번째 노드는 아래와 같이 생성되었다. head는 첫번째 노드의 주소를 반드시 따로 저장해야 한다.

 

 

다시 말하지만, 배열은 먼저 크기를 선언해서 미리 만드는 것이 특징이었으나, 연결리스트는 노드 10개인 리스트를 만들겠다고 해서 노드 10개를 미리 만드는 것이 아니다.

이제 여기에 노드를 하나하나 추가해보는 예제를 살펴볼 것이다.

 

 

 

 

 

다음 노드를 생성해보자. 

 

int main()
{
 	Node *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;
 
 ...

 

 

여기서 q -> data 는 (*q).data 와 동일하다. 

맨 마지막 코드문장 head->next = q 로 인해, 두 노드가 연결되기 시작했다.

 

 

head->next = q 로 인해, 빨간 화살표가 생성되었다.

 

 

 

맨 앞에 노드를 삽입해볼 때의 코드를 살펴보자.

 

int main()
{
 	Node *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;
    
 	q = (Node *)malloc(sizeof(Node));   // 새로운 노드 만들기
 	q->data = "Monday";
 	q->next = head;   // 원래의 head
 	head = q;    // head 는 q로 치환
 
 ...

 

연결리스트의 맨 앞에 노드 "Monday" 를 삽입하기 위해선 아래 4줄 코드를 작성해야 한다.

① q의 next 에 원래 head 주소를 넣어준다.

② head 는 q로 치환하여 첫번째 노드가 "Monday"로 되게 해주었다.

 

 

 

 

 

 

이제 연결리스트가 잘 만들어졌는지 보기 위해 "요일이 차례대로 출력되는지 확인" 해본다.

▼

 

int main()
{
 	Node *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;
    
 	q = (Node *)malloc(sizeof(Node));
 	q->data = "Monday";
 	q->next = head;
 	head = q;
    
 	Node *p = head;
    	while(p!=NULL) {
 		printf("%s\n", p->data);
 		p = p->next;     // ***
 	}
}

 

아래 4줄 코드를 생성하였다.

p 는 head 로 하여 시작 주소를 가지고 있게 한다. 그 다음 while 문을 이용해 p가 NULL이 아닌 동안, 반복하게 한다.

p의 현재 data를 출력한 다음에 p 가 다음 노드를 가리키게 한다.

 

 

 

※ 여기서 head를 굳이 p 변수에 생성하는 이유는

head 변수를 사용하게 될 경우 head는 NULL 이 될 수 있다. 그러면 head의 본 업무(첫번째 노드의 주소는 따로 저장해야 하며, 절대 잊어버려서는 안된다) 를 잃어버리는 것과 마찬가지이다. 여기선 문제가 되지 않아도 나중에 어떤 프로그램을 만들 때, 다른 프로그램에 영향을 끼칠 수도 있다.

 

따라서 head 가 첫번째 노드의 주소를 따로 저장하는 업무를 반드시 지켜야 한다.

 

 

 

 

 

 

다음 게시물은 좀 더 구체적인 연결리스트의 삽입, 삭제하는 함수들을 만들어 보겠다.