리스트 내의 각 요소는 노드(Node)라고 부른다.
링크드 리스트에서의 노드는 데이터를 보관하는 필드와 다음 노드와의 연결 고리 역할을 하는 포인터로 이루어진다.
리스트도 헤드(Head)와 테일(Tail)을 갖고 있다.
리스트의 첫 번째 노드를 헤드라고 하고 마지막 노드를 테일이라고 한다.
c언어로 표현하는 기본적 링크드 리스트 예제 구조체 사용
예제)
typedef struct testNode
{
int data; //데이터 필드
struct testNode* NextNode; // 다음 노드를 가리키는 포인터
} Node;
기본적으로 링크드 리스트를 구축하고 링크드 리스트에 있는 자료를 사용하기 위해 필요한 연산은 5개다.
- 노드 생성/소멸
- 노드 추가
- 노드 탐색
- 노드 삭제
- 노드 삽입
노드의 생성/소멸, 추가, 삭제, 삽입은 링크드 리스트 자료구조를 구축하기 위한 연산이고,
리스트 탐색은 구축되어 있는 링크드 리스트의 데이터를 활용하기 위한 연산이다.
전역 변수나 정적 변수 등이 저장되는 정적 메모리(Static Memory)
- 프로그램이 실행하면서 프로그램에서 사용될 전역 변수/정적 변수 메모리에 할당한 후 프로그램이 종료될 때 해제하는 영역
지역 변수가 저장되는 자동 메모리(Automatic Memory)
- 스택 구조로 이루어져 있어 이곳에 저장된 변수는 코드 블록 ('{'와'}의 괄호로 이루어진 블록)이 종료됨에 따라 4차원의 세계로 사라진다.
- 코드 블록이 끝나는 곳에서 자동으로 메모리를 해제하기 때문에 자동메모리라고 불린다.
마지막은 자유 저장소(Free Store)
malloc 함수 사용한 예제
// 노드 생성
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);
}
**SLL이란 Single Linked List의 약자
노드 추가 코드
void AppendNode(Node** Head, Node* NewNode)
{
if((*Head) == NULL)
{
*Head = NewNode;
}
else
{
Node* Tail = (*Head);
while(Tail -> NextNode !=NULL)
{
Tail = Tail ->NextNode;
}
Tail ->NextNode = NewNode;
}
}사용 예시 코드
Node* List NULL;
Node* NewNode NULL;
NewNode = SLL_CreateNode(117); //자유 저장소에 노드 생성
AppendNode(&List, NewNode) // 생성한 노드를 List에 추가
NewNode = SLL_CreateNode(119); // 자유 저장소에 또 다른 노드 생성
AppendNode(&List, NewNode); // 생성한 노드를 List에 추가
노드 탐색
탐색 연산은 링크드 리스트가 갖고 잇는 약점 중의 하나다.
배열이 인덱스를 이용해 즉시 원하는 요소를 취할 수 있게 하는데 반해, 링크드 리스트는 헤드부터 시작해 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야지만 원하는 요소에 접근할 수 있다.
임의의 위치에 있는 노드를 찾아 반환하는 코드
Node* GetNodeAt(Node* Head, int Location)
{
Node* Current = Head;
while(Current != NULL && (--Location) >=0)
{
Current = Current ->NextNode;
}
return Current;
}
다음과 같이 사용 가능
Node* List = NULL;
Node* MyNode = NULL;
AppendNode(&List,CreateNode(117)); // 노드를 생성해 List에 추가한다.
AppendNode(&List,CreateNode(119)); // 노드를 생성해 List에 추가
MyNode = GetNodeAt(List, 1); // 두 번째 노드의 주소를 MyNode에 저장
print("%d\n",MyNode->Data); // 119를 출력한다.
노드 삭제
노드 삭제 연산은 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산이다. 삭제하고자 하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에 연결하면 된다.
삭제 연산 코드
void 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* List = NULL;
Node* MyNode = NULL;
AppendNode(&List, CreateNode(117)); // 노드를 생성해 List에 추가
AppendNode(&List, CreateNode(119)); // 노드를 생성해 List에 추가
AppendNode(&List, CreateNode(128)); // 노드를 생성해 List에 추가
MyNode = GetNodeAt(List,1); // 두 번째 노드의 주소를 MyNode에 저장
printf("%d\n",MyNode->Data); // 119를 출력 - 1번째이므로
RemoveNode(&List, MyNode); // 두 번째 노드 제거 MyNode가 1이기 때문
DestroyNode(MyNode); // 제거가 끝난 노드는 메모리에서 완전히 소멸
노드 삽입
노드 삽입은 노드와 노드 사이에 새로운 노드를 끼워넣는 연산이다.
노드 삽입 코드
void InsertNode(Node* Current, Node* NewNode)
{
NewNode -> NextNode = Current -> NextNode; //원래 노드가 가리키고 있는 노드를 새로운 노드의 가리키는 노드로 변환
Current -> NextNode = NewNode; // 현재 노드의 가리키는 노드의 위치는 새로운 노드로 변환
}
노드 개수 세기 코드
int GetNodeCount(Node* Head)
{
int Count = 0;
Node* Current = Head;
while(Current != NULL)
{
Current = Current -> NextNode;
Count++;
}
return Count;
}
최근댓글