[링크드 리스트]
[자료구조]
자료구조란 데이터를 효율적으로 조직하고 저장하는 방법
[리스트]
만약 임의의 디렉토리 내부의 파일의 목록이 필요하다면?
=>그 크기가 얼마인지 가늠이 안되므로 배열을 얼마나 선언 할 지 정하기 힘들다
해결을 위해 필요한 자료구조는?
- 배열처럼 데이터 집합을 보관하는 기능을 가진다.
- 유연하게 크기를 바꿀 수 있어야 한다.
=>이것이 리스트 (List : 목록)
[링크드 리스트]
링크드 리스트
"노드를 연결해서 만드는 리스트"
리스트를 구현하는 여러 방법중 가장 간단한 방법이다.
노드
리스트내 각 요소는 노드 (Node : 마디) 라고 부른다.
=>노드는 데이터를 보관하는 필드 / 다음 노드와의 연결고리 역할을 하는 포인터로 구성된다.
=>노드를 엮은 링크드 리스트는 헤드 (첫번째 노트) 와 테일 (마지막 노트)을 가지고 있다 .
장점
데이터가 늘어날때마다 노드를 만들어 테일에 붙이거나 리스트 사이 새로운 노트를 끼워주는 것이 쉽다 .
=>해당 노드를 가리키는 포인터만 교환하면 되기 때문이다.
[C 언어로 표현하는 링크드 리스트의 노드]
링크드 리스트
링크드 리스트의 노드는 다음과 같은 구조체로 나타낼 수 있다.
typedef struct Node
{
int Data; //데이터 필드
struct Node* NextNode; //다음 노드를 가리키는 포인터
}Node;
[링크드 리스트의 주요 연산]
필요 연산
링크드 리스트를 구축하고 , 링크드 리스트에 있는 자료를 사용하기 위한 연산
- 노드 생성/소멸 (구축)
- 노드 추가 (구축)
- 노드 탐색 (구축)
- 노드 삭제 (구축)
- 노드 삽입 (활용)
[링크드 리스트의 주요 연산 - 생성과 소멸]
c언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가진다.
- 정적 메모리(Static Memory) : 정적 변수/전역 변수가 저장 .
- 자동 메모리(Automatic Memory) : 지역 변수가 저장 . 스택 구조로 이루어져 코드 블록 {} 이 종료되면 사라진다.
- 자유 저장소(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)데이터 베이스에서 조회해온 레코드를 순차적으로 다루는데이 적격 .
'자료구조' 카테고리의 다른 글
[자료구조] 리스트 - 03 . 환형 링크드 리스트 <구현> (0) | 2023.01.21 |
---|---|
[자료구조] 리스트 - 03 . 환형 링크드 리스트 (0) | 2023.01.20 |
[자료구조] 리스트 - 02 . 더블 링크드 리스트 <구현> (0) | 2023.01.17 |
[자료구조] 리스트 - 02 . 더블 링크드 리스트 (0) | 2023.01.16 |
[자료구조] 리스트 - 01. 링크드 리스트 < 예제 > (0) | 2023.01.15 |