-
링크드 리스트
배열 유감
배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조
리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요
링크드 리스트를 소개합니다
링크드 리스트 : 노드를 연결해서 만드는 리스트
노드 : 데이터를 보관하는 필드 + 다음 연결 고리 역할을 하는 포인터 로 구성됨
헤드(머리)와 테일(꼬리)을 가지고 있음
데이터가 늘어날 때마다 테일에 붙이면 됨
C 언어로 표현하는 링크드 리스트의 노드
typedef struct Node
{
int Data; // 데이터 필드
struct Node* NextNode ; // 다음 노드를 가리키는 포인터
} NODE ;
링크드 리스트의 주요 연산
-
노드 생성 / 소멸
지역 변수를 사용하면 함수가 끝남과 동시에 객체가 소멸되므로 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 ) ; // malloc으로 동적할당했던 node를 해제
}
-
노드 추가
// 노드 추가 함수
void SLL_AppendNode( NODE** head, NODE* NewNode )
{
// 헤드 노드가 null 이면 새로운 노드가 head
if ( *head == NULL )
{
*head = NewNode ;
}
else
{
// 테일을 찾아 연결
NODE* tail = (*head);
while( tail->NextNode != NULL )
{
tail = tail->NextNode;
}
tail->NextNode = NewNode ;
}
}
-
노드 탐색
리스트의 단점
배열이 인덱스를 이용하여 즉시 원하는 요소를 취할 수 있게 하는데 반해, 링크드 리스트는 헤드부터 시작해서 다음 노드에 대한 포인터를 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있음
// 노드 탐색 함수
NODE* SLL_GetNodeAt( NODE* head, int location )
{
NODE* current = head ;
while( current != NULL && (--location) >= 0 )
{
current = current->NextNode;
}
return current ;
}
-
노드 삭제
// 노드 제거 함수
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;
}
}
}
삭제한 노드는 SLL_DestroyNode 함수로 소멸해줌....
-
노드 삽입
// 노드 삽입 함수
void SLL_InsertAfter( NODE* current, NODE* NewNode )
{
NewNode->NextNode = current->NextNode;
current->NextNode = NewNode ;
}
-
노드 개수 세기
// 노드 개수 세기
int SLL_GetNodeCount( NODE* head )
{
int count = 0;
NODE* current = head;
while( current != NULL )
{
current = current->NextNode;
count++
}
return count;
}
링크드 리스트 예제 프로그램
- 예제 LinkedList.h
-
|
#ifndef LINKEDLIST_H #define LINKEDLIST_H
#include <stdio.h> #include <stdlib.h>
typedef int ElementType;
typedef struct tagNode { ElementType data; struct tagNode* next; } NODE;
// NODE* SLL_createNode( EelementType data ) ; 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* newHead ); void SLL_removeNode( NODE** head, NODE* remove ); NODE* SLL_getNode( NODE* head, int location ) ; int SLL_getCount( NODE* head ) ;
#endif |
- 예제 LinkedList.c
|
#include "SingleLinkedList.h"
// 노드 생성 NODE* SLL_createNode( EelementType data ) { NODE* newNode = (NODE*)malloc(sizeof(NODE)); newNode->data = data; newNode->next = 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 { // 테[일을 찾아 연결 NODE* tail = (*head); while( tail->next != NULL ) { tail = tail->next; } tail->next = newNode; } }
// 노드 삽입 void SLL_insertAfter( NODE* current, NODE* newNode ) { newNode->next = current->next; current->next = newNode; }
// 새로운 헤드 void SLL_insertNewHead( NODE** head, NODE* newHead ) { if( *head == NULL ) { (*head) = newHead; } else { newHead->next = (*head); (*head) = newNode; } }
// 노드 제거 void SLL_removeNode( NODE** head, NODE* remove ) { if( *head == remove ) { *head = remove->next; } else { NODE* current = *head; while( current != NULL && current->next != remove ) { current = current->next; }
if( current != NULL ) { current->next = remove->next; } } }
// 노드ㅡ 탐섹 NODE* SLL_getNode( NODE* head, int location ) { NODE* current = head;
while( current != NULL && (--location) >= 0 ) { current = current->next; }
return current; } int SLL_getCount( NODE* head ) { int count = 0 ; NODE* current = head;
while( current != NULL ) { current = current->next; count++; }
return count; } |
- 예제 main.c
|
#include "SingleLinkedLists.h"
void main(void) { int i = 0 ; int count = 0 ; NODE* list = NULL; NODE* current = NULL; NODE* newNode = NULL;
//추가 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_getCount( list ) ; for ( i = 0 ; i < count ; i++ ) { current = SLL_getNode( list, i ); printf("list[%d] : %d\n", i, current->data;); }
// 3번째 뒤에 삽입 current = SLL_getNode( list, 2 ) ; newNode = SLL_createNode( 3000 ) ; SLL_insertAfter( current, newNode ) ;
//출력 // 출력 count = SLL_getCount( list ) ; for ( i = 0 ; i < count ; i++ ) { current = SLL_getNode( list, i ); printf("list[%d] : %d\n", i, current->data;); }
// 모든 노드 제거 for( i = 0 ; i < count ; i++ ) { SLL_removeNode( &list, current ) ; SLL_destroyNode( current ) ; } } |
링크드 리스트의 뒷이야기
단점
- 다음 노드를 가리키려는 포인터 때문에 노드마다 4byte 메모리 추가가 필요
- 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도가 느림. 노드이 개수가 n이라면 최악의 경우 n회의 노드 탐색 루프를 실행해야함. 반면 배열은 상수 시간에 노드를 얻을 수 있음
장점
- 새로운 노드의 추가/삽입/삭제가 쉽고 빠름, 배열은 삽입,삭제가 어려움
- 현재 노드의 다음 노드를 얻어 오는 연산에 대해서는 비용이 발생하지 않음
링크드 리스트 정리
- 노드의 추가/삽입/삭제는 빠르고, 찾기 연산은 느림
-
더블 링크드 리스트
더블 링크드 리스트를 소개합니다
링크드 리스트의 탐색 기능을 개선한 자료구조
양방향 탐색이 가능한 구조
typedef struct tagNode
{
int Data; /* 데이터 필드 */
struct tagNode* PrevNode ; /* 이전 노드를 가리키는 포인터 */
struct tagNode* NextNode ; /* 다음 노드를 가리키는 포인터 */
} Node ;
더블 링크드 리스트의 주요 연산
-
노드 생성/소멸
싱글 링크드 리스트와 같음
/* 노드생성 */
Node* DLL_CreateNode(El ementType NewData)
{
Node* NewNode (Node*)malloc (sizeof (Node ));
NewNode->Data NewData ;
NewNode- >PrevNode NULL ;
NewNode- >NextNode NULL;
return NewNode ;
}
// 노드 소멸
void DLL_DestroyNode( Node* node )
{
free(node);
}
-
노드 추가
prev와 next를 연결
//< node 삽입
void DLL_appendNode( NODE** head, NODE* newNode )
{
//< head가 NULL이면 head 에 삽입
if( (*head) == NULL )
{
*head = newNode ;
}
//< head가 NULL이 아니면 tail을 찾아 tail->next에 삽입
else
{
NODE* tail = (*head);
while( tail->next != NULL )
{
tail = tail->next ;
}
tail->next = newNode ;
newNode->prev = tail;
}
}
-
노드 탐색
// 노드 탐색
NODE* DLL_getNode( NODE* head, int location )
{
NODE* current = head ;
while( current != NULL && (--location) >= 0 )
{
current = current->next ;
}
return current ;
}
-
노드 삭제
//< node 삭제
void DLL_removeNode( NODE** head, NODE* remove )
{
if ( (*head) == remove )
{
*head = remove->next ;
if( (*head) != NULL )
{
(*head)->prev = NULL ;
}
}
else
{
NODE* temp = remove ;
if( remove->prev != NULL )
{
remove->prev->next = temp->next ;
}
if( remove->next != NULL )
{
remove->next->prev = temp->prev ;
}
}
remove->prev = NULL;
remove->next = NULL;
}
-
노드 삽입
//< 노드를 찾아 삽입
void DLL_insertAfter( NODE* current, NODE* newNode )
{
newNode->next = current->next ;
newNode->prev = current ;
if( current->next != NULL )
{
current->next->prev = newNode ;
}
current->next = newNode ;
}
-
노드 개수 세기
// 노드 개수 세기
int DLL_getNodeCount( NODE* head )
{
int count = 0 ;
NODE* current = head ;
while( current != NULL )
{
current = current->next ;
count++ ;
}
return count ;
}
더블 링크드 리스트 예제 프로그램
- 예제 DoubleLinkedList.h
-
|
#ifndef _DOUBLE_LINKED_LIST_H__ #define _DOUBLE_LINKED_LIST_H__
#include <stdio.h> #include <stdlib.h>
typedef struct tagNode { int data ; tagNode* prev ; tagNode* next ; }NODE ;
//< node 생성 NODE* DLL_createNode( int newData ); //< node 소멸 void DLL_destroyNode( NODE* node ) ; //< node 삽입 void DLL_appendNode( NODE** head, NODE* newNode ) ; void DLL_insertAfter( NODE* current, NODE* newNode ) ; //< node 삭제 void DLL_removeNode( NODE** head, NODE* remove ) ; // NODE* DLL_getNode( NODE* head, int location ) ; // int DLL_getNodeCount( NODE* head ) ;
#endif |
- 예제 DoubleLinkedList.c
|
#include "stdafx.h" #include "DLL.h"
//< node 생성 NODE* DLL_createNode( int newData ) { NODE* newNode =(NODE*)malloc(sizeof(NODE));
newNode->next = NULL ; newNode->prev = NULL ; newNode->data = newData ;
return newNode ; } //< node 소멸 void DLL_destroyNode( NODE* node ) { free(node); } //< node 삽입 void DLL_appendNode( NODE** head, NODE* newNode ) { //< head가 NULL이면 head 에 삽입 if( (*head) == NULL ) { *head = newNode ; } //< head가 NULL이 아니면 tail을 찾아 tail->next에 삽입 else { NODE* tail = (*head); while( tail->next != NULL ) { tail = tail->next ; }
tail->next = newNode ; newNode->prev = tail; } } //< 노드를 찾아 삽입 void DLL_insertAfter( NODE* current, NODE* newNode ) { newNode->next = current->next ; newNode->prev = current ;
if( current->next != NULL ) { current->next->prev = newNode ; } current->next = newNode ; }
//< node 삭제 void DLL_removeNode( NODE** head, NODE* remove ) { if ( (*head) == remove ) { *head = remove->next ; if( (*head) != NULL ) { (*head)->prev = NULL ; } } else { NODE* temp = remove ;
if( remove->prev != NULL ) { remove->prev->next = temp->next ; }
if( remove->next != NULL ) { remove->next->prev = temp->prev ; } }
remove->prev = NULL; remove->next = NULL; }
// 노드 탐색 NODE* DLL_getNode( NODE* head, int location ) { NODE* current = head ;
while( current != NULL && (--location) >= 0 ) { current = current->next ; }
return current ; } // 노드 개수 세기 int DLL_getNodeCount( NODE* head ) { int count = 0 ; NODE* current = head ;
while( current != NULL ) { current = current->next ; count++ ; } return count ; } |
- 예제 main
|
// 02_DoubleLinkedList.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. //
#include "stdafx.h" #include "DLL.h"
int _tmain(int argc, _TCHAR* argv[]) { int i = 0 ; int count = 0 ; NODE* list = NULL ; NODE* newNode = NULL ; NODE* current = NULL ;
// 추가 for ( i = 0 ; i < 5 ; i++ ) { newNode = DLL_createNode(i); DLL_appendNode(&list, newNode ) ; }
// 출력 count = DLL_getNodeCount(list); for( i = 0 ; i < count ; i++ ) { current = DLL_getNode( list, i ); printf("list[%d] : %d\n", i, current->data ) ; }
// 리스트의 3번째 노드 뒤에 추가 current = DLL_getNode( list, 2 ) ; newNode = DLL_createNode( 3000 ) ; DLL_insertAfter( current, newNode ) ;
// 출력 count = DLL_getNodeCount(list); for( i = 0 ; i < count ; i++ ) { current = DLL_getNode( list, i ); printf("list[%d] : %d\n", i, current->data ) ; }
// 모든 노드 제거 count = DLL_getNodeCount( list ) ; for ( i = 0 ; i < count ; i++ ) { current = DLL_getNode( list, 0 ) ; if ( current != NULL ) { DLL_removeNode( &list, current ) ; DLL_destroyNode( current ) ; } } return 0; } |
-
환형 링크드 리스트
리스트 세계와 우로보로스, 환형 링크드 리스트
머리가 꼬리를 물고 있는 형태의 링크드 리스트
장점
시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있음
테일에 접근하는 비용이 거의 없음
테일에 추가하는 노드에 대해서 성능 개선
환형 더블 링크드 리스트의 주요 연산
-
노드 추가
// 노드 추가
void CDLL_AppendNode(NODE** head, NODE* newNode)
{
// 헤드 노드가 NULL이면 새로운 새로
if( (*head) == NULL )
{
*head = newNode;
(*head)->next = *head;
(*head)->prev = *head;
}
else
{
// 테일과 헤드 사이에 newNode 삽입
NODE* tail = (*head)->prev;
tail->next->prev = newNode;
tail->next = newNode;
newNode->next = (*head);
newNode->prev = tail;
}
}
-
노드 삭제
// 노드 제거
void CDLL_removeNode(NODE** head, NODE* remove)
{
if( *head == remove )
{
(*head)->prev->next = remove->next;
(*head)->next->prev = remove->prev;
*head = remove->next;
remove->prev = NULL;
remove->next = NULL;
}
else
{
NODE* temp = remove;
remove->prev->next = temp->next;
remove->next->prev = temp->prev;
remove->prev = NULL;
remove->next = NULL;
}
}
환형 더블 링크드 리스트 예제 프로그램
- 예제 CircularLinkedList.h
-
|
#ifndef CIRCULARLINKEDLIST_H__ #define CIRCULARLINKEDLIST_H__
#include <iostream>
typedef struct tagNode { int data ; tagNode* prev ; tagNode* next ; }NODE ;
//< node 생성 NODE* CDLL_createNode( int newData ); //< node 소멸 void CDLL_destroyNode( NODE* node ) ; // 삽입 void CDLL_appendNode( NODE** head, NODE* newNode ); // 노드 삽입 void CDLL_insertAfter(NODE* current, NODE* newNode); // 삭제 void CDLL_removeNode( NODE** head, NODE* remove ) ; // NODE* CDLL_getNode( NODE* head, int location ) ; // int CDLL_getNodeCount( NODE* head ) ;
void printNode(NODE* node);
#endif |
- 예제 CircularLinkedList.c
|
#include "CircularLinkedList.h"
//< node 생성 NODE* CDLL_createNode( int newData ) { NODE* newNode =(NODE*)malloc(sizeof(NODE));
newNode->next = NULL ; newNode->prev = NULL ; newNode->data = newData ;
return newNode ; } //< node 소멸 void CDLL_destroyNode( NODE* node ) { free(node); }
// 노드 추가 void CDLL_appendNode( NODE** head, NODE* newNode ) { // 헤드가 NULL이면 새로운 노드가 head if ( (*head) == NULL ) { *head = newNode; (*head)->next = *head; (*head)->prev = *head; } else { // 테일과 헤드 사이에 newNode 삽입 NODE* tail = (*head)->prev;
tail->next->prev = newNode; tail->next = newNode;
newNode->next = (*head); newNode->prev = tail; } } void CDLL_insertAfter(NODE* current, NODE* newNode) { newNode->next = current->next; newNode->prev = current;
current->next->prev = newNode; current->next = newNode; }
void CDLL_removeNode( NODE** head, NODE* remove ) { if( *head == remove ) { (*head)->prev->next = remove->next ; (*head)->next->prev = remove->prev ;
*head = remove->next;
remove->prev = NULL ; remove->next = NULL ; } else { NODE* temp = remove;
remove->prev->next = temp->next; remove->next->prev = temp->prev;
remove->prev = NULL; remove->next = NULL; } }
// 노드 탐색 NODE* CDLL_getNode( NODE* head, int location ) { NODE* current = head ;
while( current != NULL && (--location) >= 0 ) { current = current->next ; }
return current ; } // 노드 개수 세기 int CDLL_getNodeCount( NODE* head ) { int count = 0 ; NODE* current = head ;
while( current != NULL ) { current = current->next ; count++ ;
if( current == head ) { break; } } return count ; }
void printNode(NODE* node) { if( node->prev == NULL ) { printf("prev : NULL"); } else { printf("prev : %d", node->prev->data); } printf("current : %d", node->data);
if( node->next == NULL ) { printf("next : NULL\n"); } else { printf("next : %d\n", node->next->data); } } |
- 예제 main.c
|
#include "CircularLinkedList.h"
void main(void) { int i = 0; int count = 0; NODE* list = NULL; NODE* newNode = NULL ; NODE* current = NULL ;
// 추가 for ( i = 0 ; i < 5 ; i++ ) { newNode = CDLL_createNode(i); CDLL_appendNode( &list, newNode ) ; }
// 출력 count = CDLL_getNodeCount( list ) ; for ( i = 0 ; i < count ; i++ ) { current = CDLL_getNode(list, i); printf("list[%d] : %d\n", i, current->data); }
// 리스트의 세 번째 칸 뒤에 노드 삽입 printf("\nInserting 3000after[2]..\n\n"); current = CDLL_getNode(list, 2); newNode = CDLL_createNode(3000); CDLL_insertAfter(current, newNode);
// 리스트 출력 // 노드 수의 2배만큼 루프를 돌며 환영임을 확인 count = CDLL_getNodeCount(list); for( i = 0 ; i < count*2 ; i++ ) { if( i == 0 ) current = list; else current = current->next;
printf("list[%d] : %d\n", i, current->data); }
// 모든 노드 메모리에서 제거 printf("\nDestroing List\n"); count = CDLL_getNodeCount(list);
for( i = 0 ; i < count ; i++ ) { current = CDLL_getNode(list, 0); if( current != NULL ) { CDLL_removeNode(&list, current); CDLL_destroyNode(current); } } } |