[자료구조] linked list , double linked list , circular linked list 이해
소개
linked list는 Array list와 달리 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 Element - Element간 연결을 이용하여 리스트를 구성하여 데이터를 저장하는 자료 구조이다. 연결리스트인 linked list를 구성함에 있어 link(연결)에 대하여 파악하는 것이 가장 중요한 목적이라 할 수 있다.
linked list의 종류로 Single Linked list, Double linked list, Circular linked list, Double Circular Linked list 등이 있으며 앞으로 구현과 함께 소개하도록 하겠다.
linked list의 장점
1. 각 NODE의 중간지점에서 자료의 추가 삭제가 O(1)의 시간을 가지는 장점이 있다.
linked list 단점
1. 각 node의 특정 위치 데이터를 검색시 시간복잡도 O(n)의 시간이 걸리는 단점이 존재한다.
1. Single Linked list
Single linked list는 아래의 Structure와 같이 노드안에 Data와 Addr을 저장하는 Pointer 공간으로 이루어져있고 Pointer 변수는 다음 노드를 가리키는 구조로 되어있다.
아래의 그림에서 Head는 가장 첫번째 노드이고 Tail은 가장 마지막 노드를 가리키는 단어이다.
Structure
Node의 코드구현
typedef struct _Node
{
int data;
Node *next;
}Node;Single Linked list 활용하기
위에서 Single linked list를 활용하기 위하여 우선 Structure를 구성하였다. singly Linked list의 주요 연산을 알아보면 CRUD(Create , Read, Update, Delete) 에 기반하여 간단하게 생성 삭제 추가 출력에 대한 기능을 알아보고자 한다 .
/* 추후 중간 추가 및 정렬 함수를 추가할 예정이다 */
1. List Show 함수 ( 리스트 출력함수 )
링크드 리스트를 직접 확인을 하기위하여 우선 리스트 출력함수를 우선 개발을 진행하였다.
void Show_list(Node *node)
{
Node *cur = node->next;
printf("[ ");
while(cur != NULL)
{
printf("|%d| -> ",cur->data);
cur = cur->next;
}
printf("]\n");
}result
hdr 노드를 생성하였지만 내부에 데이터가 없기때문에 노드에 빈값이 들어가있다.
2. Node 생성함수
#define null NULL
Node *CrteNode()
{
Node *Hdr = malloc(sizeof(Node));
if(hdr == null)
printf("Fail to memory allocation\n");
else
{
hdr->next = NULL;
hdr->data = 0;
}
return hdr;
}2. Node Add function
void add_node(Node *cur, int data)
{
/*add node crte*/
Node *new_node = Crtenode(0);
if(new_node == null)
{
printf("new_node Fail to Mem allocation\n");
return;
}
if(cur == null)
{
printf("cur node or hdr No exist\n");
cur = new_node;
new_node->data = data;
printf("New_node create\n");
return ;
}
/* node link
** 1. hdr node ->next == NULL
** | hdr node |-> NULL | new_node |-> NULL
** | hdr node | -> | new_node |-> NULL
**/
if( cur->next == null){
cur->next = new_node;
new_node-> next = null;
new_node-> data = data;
}else{
Node *tmp = cur;
while( tmp->next != null)
{
tmp = tmp->next;
}
tmp->next = new_node;
new_node->next = null;
new_node->data = data;
}
printf("add data %d\n",new_node->data);
return;
}result
3. Node delete function
void total_del_node(Node *node)
{
if(node == null)
{
printf("node is null\n");
return;
}
Node *tmp = node;
Node *next;
while( tmp != null)
{
next = tmp->next;
free(tmp);
tmp = next;
}
printf("node total destroy \n");
return;
}2. Double Linked list
Double linked list는 아래의 Structure와 같이 노드안에 Data와 Addr을 저장하는 Pointer 공간으로 이루어져있고 Pointer 변수는 이전노드를 가리키는 Prev 포인터와 다음 노드를 가리키는 Next구조로 되어있다.
Structure
Node의 코드구현
typedef struct _Node
{
int data;
Node *prev;
Node *next;
}Node;Doubly Linked list 활용하기
위에서 Doubly linked list를 활용하기 위하여 우선 Structure를 구성하였다. Doubly Linked list의 주요 연산역시 Singly Linked list와 같이 간단하게 생성 삭제 추가 출력에 대한 기능을 알아보고자 한다 .
/* 추후 중간 추가 및 정렬 함수를 추가할 예정이다 */
1. List Show 함수 ( 리스트 출력함수 )
Double Linked list역시 링크드 리스트를 직접 확인을 하기위하여 우선 리스트 출력함수를 우선 개발을 진행하였다.
void Show_list(Node *node)
{
Node *cur = node->next;
if( (node == null) && (cur == null) )
{
printf(" result : node is empty \n");
return ;
}
printf("[ ");
while(cur != null)
{
printf("|%d| <-> ",cur->data);
cur = cur->next;
}
printf("]\n");
}
2. Node 생성함수
Node *Crtenode()
{
Node *hdr = malloc(sizeof(Node));
hdr->prev = null;
hdr->next = null;
hdr->data = 0;
printf("Create Node \n");
return hdr;
}2. Node Add function ( 1. Right side 2. Left Side )
void add_Rside(Node *cur, int data)
{
/*add node crte*/
Node *new_node = Crtenode(0);
if(new_node == null)
{
printf("new_node Fail to Mem allocation\n");
return;
}
if(cur == null)
{
printf("cur node or hdr No exist\n");
cur = new_node;
new_node->data = data;
printf("New_node create\n");
return ;
}
if( cur->next == null){
new_node->prev = cur;
new_node->next = null;
new_node-> data = data;
cur->next = new_node;
}else{
Node *tmp = cur;
while( tmp->next != null)
{
tmp = tmp->next;
}
new_node->prev = tmp;
new_node->next = null;
new_node->data = data;
tmp->next = new_node;
}
printf("Right side adding data... %d\n",new_node->data);
return;
}3. Node delete function
Singly linked list와 동일하게 전체 삭제를 진행해 주면 된다.
void total_del_node(Node *node)
{
if(node == null)
{
printf("node is null\n");
return;
}
Node *tmp = node;
Node *next;
while( tmp != null)
{
next = tmp->next;
free(tmp);
tmp = next;
}
printf("node total distory \n");
return;
}3. Circular Linked list
Node의 코드구현
typedef struct _Node
{
int data;
Node *next;
}Node;Circular Linked list 활용하기
위에서 Circular linked list를 활용하기 위하여 우선 Structure를 구성하였다. singly Linked list의 주요 연산을 알아보면 CRUD(Create , Read, Update, Delete) 에 기반하여 간단하게 생성 삭제 추가 출력에 대한 기능을 알아보고자 한다 .
/* 추후 중간 추가 및 정렬 함수를 추가할 예정이다 */
1. List Show 함수 ( 리스트 출력함수 )
링크드 리스트를 직접 확인을 하기위하여 우선 리스트 출력함수를 우선 개발을 진행하였다.
void Show_list(Node *node)
{
Node *cur = node->next;
printf("[ ");
while(cur != NULL)
{
printf("|%d| -> ",cur->data);
cur = cur->next;
}
printf("]\n");
}result
hdr 노드를 생성하였지만 내부에 데이터가 없기때문에 노드에 빈값이 들어가있다.
2. Node 생성함수
#define null NULL
Node *CrteNode()
{
Node *Hdr = malloc(sizeof(Node));
if(hdr == null)
printf("Fail to memory allocation\n");
else
{
hdr->next = NULL;
hdr->data = 0;
}
return hdr;
}2. Node Add function
void add_node(Node *cur, int data)
{
/*add node crte*/
Node *new_node = Crtenode(0);
if(new_node == null)
{
printf("new_node Fail to Mem allocation\n");
return;
}
if(cur == null)
{
printf("cur node or hdr No exist\n");
cur = new_node;
new_node->data = data;
printf("New_node create\n");
return ;
}
/* node link
** 1. hdr node ->next == NULL
** | hdr node |-> NULL | new_node |-> NULL
** | hdr node | -> | new_node |-> NULL
**/
if( cur->next == null){
cur->next = new_node;
new_node-> next = null;
new_node-> data = data;
}else{
Node *tmp = cur;
while( tmp->next != null)
{
tmp = tmp->next;
}
tmp->next = new_node;
new_node->next = null;
new_node->data = data;
}
printf("add data %d\n",new_node->data);
return;
}result
3. Node delete function
void total_del_node(Node *node)
{
if(node == null)
{
printf("node is null\n");
return;
}
Node *tmp = node;
Node *next;
while( tmp != null)
{
next = tmp->next;
free(tmp);
tmp = next;
}
printf("node total distory \n");
return;
}전체 코드 git
https://github.com/JungHocheul/DataStructure