1. 링크드 리스트
1-1. 특징
- 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조
- 각 노드는 다음 노드를 가리키는 포인터를 가짐.
- 각 노드를 다음 노드를 가리키는 포인터로 연결하여 만든 리스트. Single Linked List라고도 함.
- 링크드 리스트의 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 한다.
- 헤드(Head) : 첫번째 노드의 주소값을 가지고 있음(Pointer Type)
- 테일(Tail) : 마지막 노드의 주소값을 가지고 있음(Pointer Type)
1-2. 단점
- 앞에 있는 노드를 찾아갈 방법이 없다.
1-3. 배열과의 차이점
- 리스트는 주소를 통해 다른 노드로 접근하나 배열은 index 값을 통해 접근한다.
1-4. C언어로 표현하는 링크드 리스트의 노드
|
1-5. 노드의 추가
1-6. 노드의 삭제
1-7. 노드의 삽입
2. 더블 링크드 리스트
2-1. 특징
- 각 노드가 앞 노드/뒷 노드 양쪽에 대한 포인터를 모두 갖고 있어 각 노드들을 이중으로 연결하는 리스트.
2-2. 노드의 추가
2-3. 노드의 삭제
2-4. 노드의 삽입
3. 환형 링크드 리스트
- 우로보로스처럼 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트
3-1. 노드 추가
- 최초의 노드를 추가하는 경우(즉, 노드가 한 개 뿐)
- 리스트에 노드가 이미 한 개 이상 존재하는 경우에는 테일과 헤드 사이에 새 노드를 삽입한다.
- 코드
void CDLL_AppendNode(Node** Head, Node* HeadNode) { /* 헤드 노드가 NULL이라면 새로운 노드가 Head */ if((*Head) == NULL) { *Head = HeadNode; (*Head)->NextNode = *Head; (*Head)->PrevNode = *Head; } else { /* 테일과 헤드 사이에 HeadNode를 삽입한다. */ Node* Tail = (*Head)->PrevNode; Tail->NextNode->PrevNode = HeadNode; Tail->NextNode = HeadNode; HeadNode->NextNode = (*Head); HeadNode->PrevNode = Tail /* 기존의 테일을 새로운 */ /* 테일의 PrevNode가 가리킨다. */ } } |
3-2. 노드의 삭제
-코드
void CDLL_RemoveNode(Node** Head, Node* Remove){ if(*Head == Remove) { (*Head)->PrevNode->NextNode = Remove->NextNode; (*Head)->NextNode->PrevNode = Remove->PrevNode; *Head = Remove->NextNode; Remove->PrevNode = NULL; Remove->NextNode = NULL; } else { Node* Temp = Remove; Remove->PrevNode->NextNode = Temp->NextNode; Remove->NextNode->PrevNode = Temp->PrevNode; Remove->PrevNode = NULL; Remove->NextNode = NULL; } } |
