연결 리스트(Linked List)

 

 

연결 리스트란?

필요할 때마다 바구니를 하나씩 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다.

라는 개념으로 접근하면 이해하기 쉽다.

 

바구니 역할이 구조체가 되고, 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다.

그리고 구조체 Node의 변수를 가리켜 '노드'라 한다.

이는 데이터를 담는 바구니보다는 연결이 가능한 개체라는 사실에 중점을 두어 지은 이름이다.

이렇듯 구조체의 정의 하나만 가지고도 연결 리스트의 기본 원리라고 말할 수 있다.

 

이를 그림으로 표현하면 다음과 같다.

 

연결 리스트에서의 데이터 삽입

 

 

다음 임의 코드로 연결 리스트의 삽입 개념을 잡아보자.

Node * head = NULL;		// 리스트의 머리를 가리키는 포인터 변수
Node * tail = NULL;		// 리스트의 꼬리를 가리키는 포인터 변수
Node * cur = NULL;		// 저장된 데이터의 조회에 사용되는 포인터 변수

 

이들은 연결 리스트에서 주요한 역할을 하는 포인터 변수들이다.

따라서 이들이 어떻게 사용되는지 이해하는 것이 연결 리스트의 전체의 이해에 도옴이 된다.

그럼 위의 포인터 변수들이 선언된 상황을 그림으로 표현해보면,

다음과 같이 표현할 수 있다.

 

연결 리스트의 초기상태

 

위 그림에서는 프로그램이 처음 시작되었을 때

구조체 Node의 포인터 변수 head와 tail이 NULL을 가리키고 있는 상황을 보이고 있다.

 

만약 다음과 같은 코드가 있다고 가정해본다면,

while(1)
{
	.... /*일부 생략*/...
    newNode = (Node*)malloc(sizeof(Node));		// 노드 바구니의 생성
    newNode->data = readData;
    newNode->next = NULL;
    
    if(head == NULL)		// 첫 번째 노드라면!
    	head = newNode;		// 첫 번째 노드를 head가 가리키게 함
    else
    	tail->next = newNode;	// 두 번째 이후 노드라면!
    
    tail = newNode;		// 노드의 끝에 tail이 가리키게 함
}

 

 

위의 반복문에서 첫 번째 노드가 추가되는 상황을,

다시 말해서 반복문이 처음 실행되는 상황을 살펴보자.

먼저 다음 세 문장에 의해서 노드가 생성되고 또 초기화된다.

 

newNode = (Node*)malloc(sizeof(Node));		// 노드의 생성
newNode->data = readData;					// 노드에 데이터 저장
newNode->Next = NULL;						// 노드에 next를 NULL로 초기화

 

위의 코드에서 readData에 저장된 값을 2로 가정할 때,

위의 세 문장을 실행한 결과는 다음과 같다.

 

 

위의 상태에서 포인터 변수 head가 가리키는 것이 NULL이니,

이어서 다음 구문을 실행하게 된다.

 

if(head == NULL)
	head = newNode;		// 첫 번째 노드라면 첫 번째 노드를 head가 가리키게 함
else
	tail->next = newNode;

 

 

따라서 다음 그림과 같이 head가 새로운 노드를 가리키는 상태가 된다.

 

 

 

그리고 이어서 while문의 마지막에 위치한 다음 문장을 실행하게 되면

tail = newNode;		// 노드의 끝을 tail이 가리키게 함

 

그리고 그 결과는 다음과 같다.

이것이 첫 번째 노드의 추가가 완료된 상태이다.

 

 

위 그림에서 주목할 사실은 head와 tail이 첫 번째 노드를 가리키고 있다는 점이다.

이미 짐작했겠지만 head는 리스트이 머리를 가리키고 tail은 리스트의 꼬리를 가리킨다.

노드가 몇 개가 추가되건 이는 변함이 없어야 한다.

그럼 이어서 두 번째 이후의 노드를 추가하는 과정을 추적해보자.

두 번째 이후의 노드를 추가하는 과정에서의 반복문 흐름은 다음과 같다.

 

 

while(1)
{
	/* ...일부 생략...*/
    newNode = (Node*)malloc(sizeof(Node));
    newNode->data = readData;
    newNode->next =NULL;
    
    if(head == NULL)
    	head = newNode;
    else
    	tail->next = newNode;
    tail = newNode;		// 노드의 끝을 tail이 가리키게 함
}

 

 

두 번째 노드는 연결 리스트의 끝, 다시 말해서 

tail이 가리키는 노드의 뒤에 연결되어야 하기 때문에 새 노드의 생성 및 초기화 이후에는

else 구문에 담긴 다음 문장을 실행하게 된다.

 

따라서 노드의 끝을 tail이 가리키게 하는, 반복문의 마지막 문장까지 실행할 경우,

그리고 새 노드에 저장된 값을 4로 가정할 경우 그 결과는 다음과 같다.

 

 

정리하면, 연결 리스트에서 head는 첫 번째 노드를, 그리고 tail은 마지막 노드를 가리킨다.

이렇게 해서 연결 리스트의 데이터 저장에 대한 기본 개념을 잡았다.

 

 

 

연결 리스트에서의 데이터 조회

 

 

삽입을 제대로 이해했다면 조회의 기능은 직접 구현할 수도 있다.

그럼 조회와 관련된 코드를 보자.

 

if(head == NULL)
{
	printf("저장된 자연수가 존재하지 않습니다. \n");
}
else
{
	cur = head;					// cur이 리스트이 첫 번째 노드를 가리킨다
    printf("%d",cur->data);		// 첫 번째 데이터 출력
    
    while(cur->next != NULL)	// 연결된 노드가 존재한다면
    {
    	cur = cur->next;		// cur이 다음 노드를 가리키게 한다.
        printf("%d", cur->data)	// cur이 가리키는 노드를 출력한다.
    }
}

 

 

 

해당 cur를 

cur - cur->next

란 코드를 통해서 모든 노드를 가리키며 이동하게 하는 방법이다.

 

 

 

연결 리스트에서의 데이터 삭제

 

예제로 보일 삭제 관련 코드는 다음과 같다.

if(head == NULL)
{
	return 0;	// 삭제할 노드가 존재하지 않는다.
}
else
{
	Node * delNode = head;
    Node * delNextNode = head->next;
    
    printf("%d을(를) 삭제합니다. \n", head->data);
    free(delNode);		// 첫 번째 노드 삭제
    
    while(delNextNode != NULL)		// 두 번째 노드 삭제
    {
    	delNode = delNextNode;
        delNextNode = delNextNode->next;
        
        printf("%d을(를) 삭제합니다. \n",delNode->data);
        free(delNode);
    }
}

 

위 코드는 모든 노드의 소멸과정을 보이고 있다.

위 코드는 삭제와 관련이 있는 코드이지만 실제 연결리스트의 삭제방식은 위와 방식과는 차이가 있다.

예를 들어서 중간에 위치한 노드의 삭제방식은 위와 다르다는 점을 들 수있다.

위 코드는 head가 가리키는 노드의 삭제방법을 보일 뿐이다.

 

또한 여기서 삭제될 노드 (delNextNode)를 가리키는 이유는 

head가 가리키는 노드를 그냥 삭제해 버리면, 그 다음 노드에 접근이 불가능하기 때문이다.

 

즉 삭제될 노드가 가맄는 다음 노드의 주소 값을 별도로 저장하지 않으면

다음 노드에 접근이 불가하게 된다.

 

이는 다음 노드를 가리키는 포인터를 가져올 방법이 없어지는 현상을 방지하기 위해서

주소 값을 별도로 저장하는 것이다.

 

 

 

 

 

해당 게시글은 윤성우의 열혈 자료구조를 기반으로 제작되었습니다.