■Double Linked List■

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#ifndef DLIST_H
#define DLIST_H
 
#include <stdlib.h>
 
typedef struct DListElmt_ {
 
void               *data;
struct DListElmt_  *prev;
struct DListElmt_  *next;
 
} DListElmt;
 
 
typedef struct DList_ {
 
int                size;
 
int                (*match)(const void *key1, const void *key2);
void               (*destroy)(void *data);
 
DListElmt          *head;
DListElmt          *tail;
 
} DList;
cs
#Double Linked List는 Single Linked List와 비교하면 prev라는 포인터가 하나더 붙어 있으며 역방향으로의 순회가 가능하다.



대표적으로 insert를 구현하면서 이해를 해보면 delete,find등 다른 구현은 쉽게할 수있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dlist_init(DList *list, void (*destroy)(void *data)) {
 
/*****************************************************************************
*                                                                            *
*  Initialize the list.                                                      *
*                                                                            *
*****************************************************************************/
 
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
 
return;
 
}

cs

List의 초기화 부분이며 head와 tail은 리스트의 첫과 끝을 가리키며 size는 할당된 노드의 수를 말한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
{
DListElmt           *new_element;
    
    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
   return -1;
    new_element->data = (void *)data;
    
    if (element == NULL) {
   if (dlist_size(list) == 0)
{
       list->head = new_element;
       list->head->prev = NULL;
       list->head->next = NULL;
       list->tail = new_element;
}
 
else 
{
    new_element->next=list->tail->next;
    list->tail->next=new_element;
    list->tail = new_element;
    list->tail->prev=list->head;
}
}
else {
      if (dlist_size(list) == 0)
{
       list->head = new_element;
       list->head->prev = NULL;
       list->head->next = NULL;
       list->tail = new_element;
}
 
else 
{
    new_element->next=element->next;
    element->next=new_element;
    element = new_element;
    new_element->prev=element;
}
    
}
list->size++;
return 0;
}
}
cs

1. 전달된 노드의 값이 NULL인지 존재하는지를 구분한다. (노드가 존재하면 그 노드를 기준으로 insert 한다.)
2. size가 0인지를 즉, List안에 처음으로 들어갈 노드인지 아닌지를 체크한다.
3.
  if (dlist_size(list) == 0)
{
       list->head = new_element;
       list->head->prev = NULL;
       list->head->next = NULL;
       list->tail = new_element;
}
size가 0, List안에 처음으로 들어갈 때의 노드를 A라고 하자, 하나 밖에 없으므로 head와 tail은 A_node를 가리키고,
A_node의 앞,뒤에는 아무것도 없으므로 NULL값을 넣어준다. 
list->head(list의 head=new_element head가 new_element를 가리킨다.)
list->head->prev = NULL(head가 가리키는 노드의 prev에 NULL을 넣는다.)
4.
else 
{
    new_element->next=list->tail->next;
    list->tail->next=new_element;
    list->tail = new_element;
    list->tail->prev=list->head;
}

기존에 A_node가 있을 때 B_node가 들어간다고 가정한다면

먼저  B_node의 next에 list->tail->next(즉, A_node의 next값을 넣어준다(현재 A_node의 next값은 NULL이다)

list->tail->next(A_node의 next)는 B_node를 가리킨다.

list->tail(List의 끝은)B_node를 가리키고

list->tail->prev(B_node의 prev)는 list->head(A_node)를 가리킨다.


*전달된 노드가 있을 시 list->tail를 element로 바꿔주면 되고 현재는 insert_next로 구현하였고 insert_prev로 구현할 수도 있다.

예) insert_next : insert- 1 2 3 4    insert된 node -4 3 2 1 


'자료구조' 카테고리의 다른 글

[자료구조_Day5]biTree,bsTree  (0) 2018.11.06
[자료구조_Day4]Chained Hash Tables  (0) 2018.11.06
[자료구조_Day3]Stack  (0) 2018.11.06
[자료구조_Day3]Set  (0) 2018.11.06
[자료구조_Day2]Double Circular Linked List  (0) 2018.10.28

+ Recent posts

티스토리툴바