[자료구조] ch 01 리스트 (1)

1.1 리스트 ADT

 

1.1.1 리스트의 개념

- 목록 형태로 이뤄진 데이터 형식

- 노드(node) : 리스트의 목록을 이루는 개별 요소 

- 머리(head) : 노드 목록에서 첫 번째 노드 

- 꼬리(Tail) : 노드 목록에서 마지막 노드 

- 리스트의 길이는 헤드부터 테일까지 이르는 노드 개수와 같음

 

1.1.2 리스트와 배열 비교 

 

- 배열은 생성하는 시점에 반드시 배열의 크기를 지정해줘야 하고 생성한 후에는 그 크기를 변경할 수 없음

- 리스트는  배열처럼 데이터 집합 보관 기능을 가지면서도 배열과 달리 유연하게 크기를 바꿀 수 있는 자료구조 

 

 

1.2 링크드 리스트 

 

링크드 리스트(Linked List)

 - 노드를 연결해서 만든 리스트 

 - 링크드 리스트의 노드는 데이터를 보관하는 필드, 다음 노드와 연결고리 역할을 하는 포인터로 이루어짐

 

 

1.2.1 링크드 리스트의 노드 표현

 

- 노드를 표현하는 방법

typedef int ElementType;

typedef struct tagNode
{
  ElementType Data; //데이터
  struct tagNode* NextNode; //다음 노드 
 } Node;

- 선언한 Node 구조체로 인스턴스 만들기

Node MyNode;

 

1.2.2 링크드 리스트의 주요 연산 

 

- 자료구조를 구축하기 위한 연산( 노드 생성/소멸/추가/삽입)과 자료구조에 저장된 데이터를 활용하기 위한 연산(노드 탐색) 필요 

 

1) 노드 생성/ 소멸 연산

 

 - malloc() 함수를 사용하여 노드를 힙에 생성

Node* NewNode = (Node*)malloc(sizeof(Node));

- malloc() 함수는 sizeof 연산자가 측정한 노드 구조체의 크기만 한 메모리를 힙에 할당하고 NewNode 포인터에 그 메모리 주소를 저장 

 

노드 생성 함수 SLL_CreateNode

Node* SLL_CreateNode(ElementType NewData) 
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    
    NewNode->Data = NewData; //데이터를 저장
    NewNode->NextNode = Null; //다음 노드에 대한 포인터는 NULL로 초기화 
    
    return NewNode; //노드의 주소 반환
 }

 

노드 소멸 함수 SLL_DestroyNode

 - 노드가 존재하는 주소를 가리키는 포인터를 입력받아 free() 함수에 넘겨 해당 노드를 소멸시킴

void SLL_DestroyNode(Node* Node)
{
  free(Node);
}

 

2) 노드 추가 연산

 

 - 링크드 리스트의 꼬리 노드 뒤에 새로운 노드를 만들어 연결

 - SLL_CreateNode() 함수를 이용하여 힙에 노드를 생성한 다음, 새로 생성한 노드의 주소를 꼬리의 NextNode 포인터에 저장 

 

노드 추가 함수 SLL_AppendNode

void SLL_AppendNode(Node**Head, Node* NewNode)
{
   //머리 노드가 NULL이라면 새로운 노드가 Head가 됨
   if( (*Head) == NULL) 
   {
      *Head = NewNode;
   }
   else
   {
      //꼬리를 찾아 NewNode에 연결
      Node *Tail = (*Head);
      while( Tail->NextNode != NULL) 
      {
      	 Tail = Tail->NextNode;
      }
      
      Tail->NextNode = NewNode;
    }
}

- Node *head가 아니라 Node **head인 이유 

Node* List = NULL;
Node* NewNode = NULL;
NewNode = SLL CreateNode(117);
SLL_AppendNode(List, NewNode);

 - 포인터가 가진 값이 아닌, 포인터 자신의 주소를 넘겨야 함

 - AppendNode() 함수의 첫 번째 매개 변수를 Node**로 선언하면 Head 포인터 자신의 주소를 넘길 수 있음

 - Head 포인터는 List 포인터 변수의 '주소'를 가리키고, 이 주소를 이용하여 List가 NewNode의 주소 (힙에 할당된 117 노드의 주소)를 가리키도록 함

 

3) 노드 탐색 연산

 

- 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 개수만큼 거쳐서 원하는 요소에 접근

- 찾고자 하는 요소가 N번째에 있다면 N-1개의 노드를 거쳐야 함

 

노드 탐색 함수 SLL_GetNodeAt

 - 링크드 리스트 내에서 임의의 위치에 있는 노드를 찾아서 반환 

Node* SLL_GetNodeAt(Node* Head, int Location)
{
   Node* Current = Head;
   
   while(Current != NULL && (--Location) >= 0)
   {
   	  Current = Current -> NextNode;
   }
   
   return Current;
}

 

4) 노드 삭제 연산

 

- 링크드 리스트 내 임의의 노드를 제거

- 삭제하고자 하는 노드를 찾은 후 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에 연결

 

 

노드 삭제 함수 SLL_RemoveNode()

void SLL_RemoveNode(Node** Head, Node* Remove)
{
   if( *Head == Remove)
   {
      *Head = Remove->NextNode;
   }
   else
   {
      Node* Current = *Head;
      while( Current != NULL && Current->NextNode != Remove)
      {
      	 Current = Current->NextNode;
      }
      
      if( Current != NULL)
      	Current->NextNode = Remove->NextNode;
    }
}

 

5) 노드 삽입 연산 

 

- 노드와 노드 사이에 새로운 노드 끼워 넣기

- 이전 노드의 NextNode 포인터가 새 노드를 가리키게 하고, 새 노드의 NextNode 포인터가 다음 노드를 가리키게 함

 

노드 삽입 함수 SLL_InsertAfter()

void SLL_InsertAfter(Node* Current, Node* NewNode)
{
	NewNode->NextNode = Current->NextNode;
    Current->NextNode = NewNode;
}

 

6) 노드 개수 세기 연산

 

- 노드의 개수를 세는 (리스트의 길이를 재는 연산)

- 링크드 리스트 내에 존재하는 노드의 개수를 세어 그 결과를 반환

 

노드 개수 세기 함수 SLL_GetNodeCount()

int SLL_GetNodeCount(Node*Head)
{
	int Count=0;
    Node* Current = Head;
    
    while( Current != NULL )
    {
    	Current = Current-> NextNode;
        Count++;
    }
    
    return Count;
}

 

 

1.2.3 링크드 리스트 예제 프로그램 

 

- 링크드 리스트의 기본 연산을 수행하는 함수가 선언된 LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
	struct tagNode* NextNode;
}Node;

//함수 원형 선언
Node* SLL_CreateNode(ElementType NewData);
void SLL_DestroyNode(Node* Node);
void SLL_AppendNode(Node** Head, Node* NewNode);
void SLL_InsertAfter(Node* Current, Node* NewNode);
void SLL_InsertnewHead(Node** Head, Node* NewNode);
void SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int SLL_GetNodeCount(Node* Head);

#endif

 

- 함수를 구현하는 LinkedList.c

#include "LinkedList.h"

//노드 생성
Node* SLL_CreateNode(ElementType NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData; //데이터를 저장
	NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화 

	return NewNode; //노드의 주소를 반환
}

//노드 소멸 
void SLL_DestroyNode(Node* Node)
{
	free(Node);
}

//노드 추가 
void SLL_AppendNode(Node** Head, Node* NewNode)
{
	//헤드 노드가 NULL이라면 새로운 노드가 Head가 됨
	if ((*Head) == NULL)
	{
		*Head = NewNode;
	}
	else
	{
		//꼬리를 찾아 NewNode를 연결
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL)
		{
			Tail = Tail->NextNode;
		}

		Tail->NextNode = NewNode;
	}
}

//노드 삽입
//특정 노드 뒤에 새로운 노드 삽입
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;
}

//헤드 앞에 새로운 헤드 삽입
void SLL_InsertNewHead(Node** Head, Node* NewHead)
{
	if (Head == NULL)
	{
		(*Head) = NewHead;
	}
	else
	{
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}
}

//노드 제거 
void SLL_RemoveNode(Node** Head, Node* Remove)
{
	if (*Head == Remove)
	{
		*Head = Remove->NextNode;
	}
	else
	{
		Node* Current = *Head;
		while (Current != NULL && Current->NextNode != Remove)
		{
			Current = Current->NextNode;
		}

		if (Current != NULL)
			Current->NextNode = Remove->NextNode;
	}
}

//노드 탐색
Node* SLL_GetNodeAt(Node* Head, int Location)
{
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0)
	{
		Current = Current->NextNode;
	}

	return Current;
}

//노드 개수 세기
int SLL_GetNodeCount(Node* Head)
{
	int Count = 0;
	Node* Current = Head;

	while (Current != NULL)
	{
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

 

- 구현된 내용을 테스트하는 Test_LinkedList.c

#include "LinkedList.h"

int main(void)
{
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* Current = NULL;
	Node* NewNode = NULL;

	//노드 5개 추가 
	for (i = 0; i < 5; i++)
	{
		NewNode = SLL_CreateNode(i);
		SLL_AppendNode(&List, NewNode);
	}

	NewNode = SLL_CreateNode(-1);
	SLL_InsertnewHead(&List, NewNode);

	NewNode = SLL_CreateNode(-2);
	SLL_InsertnewHead(&List, NewNode);

	//리스트 출력
	Count = SLL_GetNodeCount(List);
	for (i = 0; i < Count; i++)
	{
	    Current = SLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//리스트의 세 번째 노드 뒤에 새 노드 삽입
	printf("\nInserting 3000 After [2]...\n\n");

	Current = SLL_GetNodeAt(List, 2);
	NewNode = SLL_CreateNode(3000);

	SLL_InsertAfter(Current, NewNode);

	//리스트 출력
	Count = SLL_GetNodeCount(List);
	for (i = 0; i < Count; i++)
	{
		Current = SLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//모든 노드를 메모리에서 제거 
	printf("\nDestroying List...\n");

	for (i = 0; i < Count; i++)
	{
		Current = SLL_GetNodeAt(List, 0);

		if (Current != NULL)
		{
			SLL_RemoveNode(&List, Current);
			SLL_DestroyNode(Current);
		}
	}

	return 0;
}

 

1.2.4 링크드 리스트의 장단점

 

1) 링크드 리스트의 단점

 

 - 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리 필요

 - 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기까지 시간도 많이 소요됨. 가령 n번째 위치에 있는 노드에 접근하려면 n회의 노드 탐색 루프를 실행해야 해당 위치의 노드에 접근 가능 

 

2) 링크드 리스트의 장점

 

 - 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠름

 - 현재 노드의 다음 노드를 얻어오는 연산에 대해서는 비용이 발생하지 않음