[C] 자료 구조 # 단일 연결 리스트 Single Linked List

# 연결 리스트

각 노드가 데이터와 다음 노드를 가리킬 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료 구조입니다.

데이터 노드가 3개 있는 연결 리스트의 구조

- 배열과 다른 점

세 개의 데이터가 있는 배열[3]이 있다면 배열[0]부터 배열[2]까지 메모리의 연속된 곳에 자리하게 됩니다.

연결리스트는 각 노드가 각자 생성될 때 할당받은 다른 메모리 주소를 갖습니다.

그래서 다음 노드의 주소를 가리키는 포인터가 필요한 것입니다.

 

- 장단점

데이터의 추가 삭제가 빠릅니다. 시간복잡도 O(1)

특정 위치의 데이터 검색이 오래걸립니다. 시간복잡도 O(n)

 

- 노드 Node

노드에는 각종 데이터 변수와 다음 노드를 가리킬 포인터 변수가 필요합니다.

따라서 여러가지 타입의 집합체인 구조체로 정의합니다.

struct Node{	// 노드 이름
    int value;	// 데이터
    Node *next;	// 포인터
}

 

# 예제 코드

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

// 노드 정의
struct Node{
	int value;
	Node *next;
};
Node *head;	// 헤더 선언

void InitList(){	// 초기화
	head = (Node*)malloc(sizeof(Node));
	head->next=NULL;
}

// Target 노드 뒤에 aNode를 삽입합니다.
Node *InsertNode(Node *Target, Node *aNode){ 
	Node *New;
	
	New = (Node*)malloc(sizeof(Node));
	*New = *aNode;
	
	New->next = Target->next;
	Target->next = New;
	
	return New;
}

// Target 노드 뒤의 노드를 삭제합니다.
bool DelNode(Node *Target){	
	Node *del;
	
	del = Target->next; 
	if(del==NULL) return false;
	Target->next = del->next;
	free(del);
	return true;
}

// 전체 노드 삭제 및 메모리 해제
void ClearAll()	
{
	while(DelNode(head)){
		;
	}
	free(head);
	head = NULL;
}

int main()
{
 	int i;
 	Node *now, temp;
 	
 	InitList();
    
    now = head;
    for(i=1; i<=5; i++){
    	temp.value=i;
    	now = InsertNode(now, &temp);
	}
		
	for(now=head->next; now; now=now->next){
    	printf("%d\n", now->value);
	}
	
    ClearAll();
	return 0;
}

출력결과
1
2
3
4
5

 

- 노드 삽입 

1) 새 노드를 생성합니다. 아직 포인터로 연결되지 않았기 때문에 연결 리스트의 삽입된 것이 아닙니다.

 

2) 새 노드의 포인터로 다음 노드의 주소를 가리킵니다. 
    이 때 다음 노드의 주소는 Target 노드의 포인터를 복사하여 대입합니다.

    그래서 Target 노드의 포인터로 새 노드의 주소를 먼저 가리키면 안됩니다.

    다음 노드를 가리키는 주소를 잃어버리기 때문입니다.

 

3) Target 노드의 포인터로 새 노드의 주소를 가리킵니다.

    방금 생성한 노드의 주소를 바로 대입합니다.

 

 

 

- 노드 삭제

 

1) Target노드의 포인터로 다음 노드를 가리킵니다.
    연결 리스트의 포인터는 앞 노드에서 다음노드를 가리키므로
    처음부터 지울 노드를 찾을 수가 없습니다.

    따라서 Target 노드의 뒤쪽 노드를 삭제할 수 있습니다.

 

2) Tartget의 다음 노드의 메모리 할당을 해제합니다.

 

 

 

- 노드 순회

 

1) head 노드는 전역변수로 선언해 놓았기 때문에 바로 head->next에 접근할 수 있습니다.

 

2) 반복적으로 ->next의 주소를 따라가면 차례대로 노드에 접근할 수 있습니다.

 

3) ->next가 null인 경우 마지막 노드입니다.

 

 

- 노드 메모리 해제

malloc으로 할당된 메모리는 직접 해제하지 않으면 프로그램이 종료되기 전까지 계속 메모리를 차지하고 있으므로,

사용 후에는 꼭 해제하는 습관을 들이면 좋습니다.