[자료구조] 리스트 - 01 . 링크드 리스트

[링크드 리스트]

[자료구조]

자료구조란 데이터를 효율적으로 조직하고 저장하는 방법

 

[리스트]

만약 임의의 디렉토리 내부의 파일의 목록이 필요하다면?

=>그 크기가 얼마인지 가늠이 안되므로 배열을 얼마나 선언 할 지 정하기 힘들다

 

해결을 위해 필요한 자료구조는?

• 배열처럼 데이터 집합을 보관하는 기능을 가진다.
• 유연하게 크기를 바꿀 수 있어야 한다.

=>이것이 리스트 (List : 목록)

 

[링크드 리스트]

 

링크드 리스트

"노드를 연결해서 만드는 리스트"

리스트를 구현하는 여러 방법중 가장 간단한 방법이다.

 

노드

리스트내 각 요소는 노드 (Node : 마디) 라고 부른다.

=>노드는 데이터를 보관하는 필드 / 다음 노드와의 연결고리 역할을 하는 포인터로 구성된다.

---

=>노드를 엮은 링크드 리스트는 헤드 (첫번째 노트) 와 테일 (마지막 노트)을 가지고 있다 .

---

장점

데이터가 늘어날때마다 노드를 만들어 테일에 붙이거나 리스트 사이 새로운 노트를 끼워주는 것이 쉽다 .

=>해당 노드를 가리키는 포인터만 교환하면 되기 때문이다.

 

[C 언어로 표현하는 링크드 리스트의 노드]

링크드 리스트

링크드 리스트의 노드는 다음과 같은 구조체로 나타낼 수 있다.

typedef struct Node
{
    int Data;			//데이터 필드
    struct Node* NextNode;	//다음 노드를 가리키는 포인터
}Node;

[링크드 리스트의 주요 연산]

필요 연산

링크드 리스트를 구축하고 , 링크드 리스트에 있는 자료를 사용하기 위한 연산

• 노드 생성/소멸 (구축)
• 노드 추가 (구축)
• 노드 탐색 (구축)
• 노드 삭제 (구축)
• 노드 삽입 (활용)

[링크드 리스트의 주요 연산 - 생성과 소멸]

c언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가진다.

1. 정적 메모리(Static Memory) : 정적 변수/전역 변수가 저장 .                                                                                                        
2. 자동 메모리(Automatic Memory) : 지역 변수가 저장 . 스택 구조로 이루어져 코드 블록 {} 이 종료되면 사라진다.                        
3. 자유 저장소(Free Store) : 사용자가 직접 메모리를 관리해야 한다.                                                                                                코드 블록으로 부터의 자유는 메모리의 안전한 해제라는 책임을 동반한다.

Q . 노드는 자동 메모리와 자유 저장소 어디에 있어야 할까 ?

1 . 자동 메모리

//노드 생성 - 자동 메모리

Node* CreateNode(int newData)
{
    Node newNode;			//자동 메모리에 새 노드 생성
    newNode.Data=newData;
    newNode.NextNode=null;
    
    return &newNode;			//newNode가 생성된 메모리의 주소를 반환
}					//코드 블록의 끝에서 newNode는 자동 메모리에서 제거.

Node*myNode=CreateNode(117);		//myNode는 할당되지 않은 메모리를 가리킨다.

2 . 자유 저장소

자유 저장소에 저장을 하려면 malloc() 함수가 필요하다

void* malloc(size_t size)

malloc()함수의 반환형은 void*로 어떤 형이라도 가리킬 수 있다.

=>malloc함수가 할당한 자유 저장소의 메모리 주소를 어떤 형의 포인터로도 가리 킬 수 있음을 의미한다 .

 

malloc함수의 매개변수의 자료형이자 sizeof 연산자의 반환형인 size_t는 typedef문을 사용하여 unsigned int형의 별칭.

즉 ,size_t는 unsigned int형이라는 것이다.

//노드를 자유저장소에 저장

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

//sizeof 연산자가 측정한 노드 크기만큼 자유저장소에 할당한 후 NewNode에  그 메모리 주소를 저장 .

이를 통해 1의 함수를 고쳐보자.

Node * CreateNode(Element newData)
{
    Node * newNode=(Node*)malloc(sizeof(Node));

    newNode->Data=newData;		//데이터를 저장
    newNode->NextNode=null;		//다음 노드에 대한 포인터는 null
    return newNode;			//노드의 주소 반환
}

노드의 소멸은 ?

void DestroyNode(Node* Node)
{
	free(Node);		//노드가 존재하는 주소를 가리키는 포인터를 free 함수에 넘겨 노드를 소멸.
}

cf ) SLL

=>Singly Linked List

:한쪽 방향으로만 엮여 있다. DLL(더블 링크드 리스트 (양쪽 방향으로 서로 엮여 있다))도 존재한다.

 

[링크드 리스트의 주요 연산 - 추가]

노드 추가 연산은 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결함을 의미한다 . 

노드를 추가하는 함수는 이렇다.

void SLL_AppendNode(Node** Head , Node* NewNode)
{
	if((*Node)==null
    {
    	*Head=NewNode
    }
    else
    {
    	Node*Tail = (*Head);
        //Tail을 찾아 NewNode를 연결한다.
        while(Tail->NextNode!=null)
    	{
        	Tail= Tail->NextNode;
        }
        
        Tail->NextNode=NewNode;
    }
}

사용의 예는 이렇다

Node* List=NULL;
Node* NewNode=NUll;

NewNode= CreateNode(117);		//자유 저장소에 노드 생성
AppendNode(&List , NewNode);	//생성한 노드를 List에 추가

왜 ApendNode는 **가 필요할까?

1 . void ApendNode(Node* _Head , Node* _NewNode) 라면

int main(void)
{
	Node* List=NULL;
    Node * NewNode=NULL;
    
    NewNode=CreateNode(117);
    AppendNode(List , NewNode);
    
}

=>List와 NewNode를 선언하면 자동 메모리에 두 포인터 변수가 생성된다.

CreateNode 로 자유 저장소에 117을 가진 노드가 생성 , NewNode는 해당 주소를 가리킨다 .

AppendNode()가 호출되면 매개변수들이 자동 메모리에 생성되고 , List는 -Head에 / NewNode는 _NewNode에 자신이 가지고 있는

메모리의 주소를 "복사해서" 넣는다 .

 

포인터는 '메모리 주소'를 담는 변수이다 .Append함수가 호출시 List 변수의 "주소값"만 복사했을뿐, 해당 변수의 주소 자체는 전달되지 않았다. 그렇기에 Append 함수가 끝나는 코드블록에서 매개변수는 사라져 ,List는 여전히 NUll인체로 남게 되는 것이다.

 

2 . void ApendNode(Node** _Head , Node* _NewNode) 라면

=>Head 포인터 자신의 주소를 넘길 수 있다 . _Head 포인터는 List 포인터 변수의 "주소"를 가리키게 되고 , 이를 통해
List 가 NewNode의 주소 (자유 메모리에 할당된 117 노드의 주소)를 가리키게 되는 것이다. 그래서 ** 를 사용한다.

 

[링크드 리스트의 주요 연산 - 탐색]

탐색은 링크드 리스트의 약점이다 . 

배열이 인덱스를 이용 , 즉시 원하는 요소를 취하는데 반해 , 링크드 리스트는 헤드부터 차근 차근 노드의 수를 세어나가야만

원하는 요소에 접근이 가능하기 때문이다 .

//노드 탐색
Node* SLL_GetNodeAt(Node * Head , int location)
{
	Node * Current = Head;
    
    while(Current!=NULL ** (--location)>=0)
    {
    	Current=Head->NextNode;
    }
    return Current;
}

Node * List=Null;
Node* NewNode=Null;

 AppendNode(&List,CreateNode(117));	//노드를 생성후 List에 추가
AppendNode(&List,CreateNode(109));	//노드를 생성후 List에 추가

MyNode = GetNodeAt(List,1);	//두번째 노드의 주소를 MyNode에 저장
Printf("%d\n",MyNode->Data);	//109가 출력

=>사용은 간단하지만 내부 구현은 비효율적이다 . 

 

[링크드 리스트의 주요 연산 - 삭제]

링크드 리스트에서 임의의 노드를 제거한다 .삭제하려는 노드를 찾고 , 해당 노드의 다음 노드를 이전 노드의 NextNode에 연결한다 .

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 !=Nulll)
    {
    	Current - >NextNode=Remove->NextNode;
    }
}

//삭제한 노드는 달리 쓸 곳이 없다면 바로 삭제하는 것이 좋다.

호출의 예는 이렇다 . 

Node * List;
Node * MyNode;

AppendNode(&Head,CreateNode(117));
AppendNode(&Head,CreateNode(119));
AppendNode(&Head,CreateNode(121));

MyNode = GetNodeAt(List , 1);
Sll_RemoveNode(&List,MyNode);
Destroy(MyNode);	//링크드 리스트에서 제거한 노드를 메모리에서 소멸시킨다

[링크드 리스트의 주요 연산 - 삽입]

노드와 노드 사이에 새로운 노드를 끼운다

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

[링크드 리스트의 주요 연산 - 노드 수 세기]

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

int CountNode(Node * Head)
{
	int Count=0;
    Node* CurrentNode = Head;
    while(CurrentNode!==null)
    {
    	CurrentNode=CurrentNode->NextNode;
    	count++;
    }
    return count;
}

[링크드 리스트 총평]

단점

• 다음 노드를 가리키려는 포인트때문에 4byte가 추가로 필요하다
• 특정 위치에 있는 노드를 얻는 비용이 크며 , 속도가 느리다. (노드의 개수가 n개라면 최악의 경우 n번의 노드 탐색 루프를 실행해야 한다) 반면 배열은 상수 시간에 노드를 얻을 수 있다 .

장점

• 새로운 노드의 추가 / 삽입 / 삭제가 쉽고 빠르다. 반면 배열은 요소의 삽입 삭제가 어렵다
• 현재 노드의 다음 노드를 얻어오는 연산에 비용이 발생 하지 않는다

결론

=>"노드의 추가/삽입/삭제가 빠르나 특정 위치의 노드를 찾는 연산은 느리다" .

따라서 링크드 리스트는 레코드의 추가/삽입/삭제가 잦고 데이터의 조회가 드문 곳이 적절하다 . 

ex)데이터 베이스에서 조회해온 레코드를 순차적으로 다루는데이 적격 .