이중 연결 리스트이다.

참고문헌 : C 로 배우는 알고리즘 1


/************************************************************************/
/* DoubledLinkedList.cpp : 이중 연결 리스트 구현                        */
/* 이 자료구조에서는 단순 연결 리스트와 비교할 때      */
/* 다음 노드뿐만 아니라 이전노드도 링크로 가지고      */
/* 접근할 수 있다는 것이 장점이다.          */
/* 하나의 링크를 더 사용하기 때문에 단순 연결 리스트보다는 노드당  */
/* 2 ~ 4 바이트 정도 더 소요된다.          */
/************************************************************************/

#include <STDIO.H>
#include <MALLOC.H>

typedef struct _dnode
{
 int key;  /* 정보 저장 */
 struct _dnode *prev; /* 바로 전의 노드를 가리키는 링크 */
 struct _dnode *next; /* 바로 뒤의 노드를 가리키는 링크 */
} dnode;

dnode *head, *tail;

/************************************************************************/
/* 함수명 : init_dlist                                                  */
/* 이중 연결 리스트를 초기화한다.          */
/************************************************************************/
void init_dlist( void )
{
 head = (dnode*)malloc(sizeof(dnode));
 tail = (dnode*)malloc(sizeof(dnode));
 head->next = tail;  
 head->prev = head;
 tail->next = tail;
 tail->prev = head;
}

/************************************************************************/
/* 함수명 : insert_dnode_ptr                                            */
/* 포인터 t 와 정수 k 를 입력받아 t 앞에 k 를 가지는 노드를 삽입한다. */
/************************************************************************/
dnode *insert_dnode_ptr(int k, dnode *t)
{
 dnode *i; // 삽입될 노드
 // head 앞에는 삽입할 수 없음
 if(t == head)
  return NULL;
 i = (dnode*)malloc(sizeof(dnode));
 i->key = k;
 t->prev->next = i; // t 앞 노드의 다음은 i 노드
 i->prev = t->prev; // i 의 앞은 t 의 앞 노드
 t->prev = i;  // t 의 앞은 i 노드
 i->next = t;  // i 의 다음은 t 노드
 return i;
}

/************************************************************************/
/* 함수명 : delete_dnode_ptr                                            */
/* 인자로 주어진 노드의 포인터 p 를 연결리스트에서 삭제한다.   */
/************************************************************************/
int delete_dnode_ptr(dnode *p)
{
 if(p == head || p == tail) // head, tail 은 삭제할 수 없음
  return 0;
 p->prev->next = p->next; // p 의 prev 의 next 는 p 의 next 노드
 p->next->prev = p->prev; // p 의 next 의 prev 는 p 의 prev 노드
 free(p);
 return 1;
}

/************************************************************************/
/* 함수명 : find_dnode                                                  */
/* 주어진 정수를 key 로 가지는 노드를 찾는다.       */
/************************************************************************/
dnode *find_dnode(int k)
{
 dnode *s;
 s = head->next;
 while(s->key != k && s != tail) // key 가 아니거나 tail 이 아닐동안 loop
  s = s->next;
 return s;
}

/************************************************************************/
/* 함수명 : delete_dnode                                                */
/* 인자를 key 로 가지는 노드를 삭제한다.        */
/************************************************************************/
int delete_dnode(int k)
{
 dnode *s;
 s = find_dnode(k); // k 를 key 로 갖는 노드를 찾는다.
 if(s != tail) // s 가 tail 이 아니면 찾은 것
 {
  s->prev->next = s->next;
  s->next->prev = s->prev;
  free(s);
  return 1;
 }
 return 0;
}

/************************************************************************/
/* 함수명 : insert_dnode                                                */
/* t 를 key 로 갖는 노드 앞에 k 를 key 로 갖는 노드를 삽입    */
/************************************************************************/
dnode *insert_dnode(int k, int t)
{
 dnode *s;
 dnode *i = NULL;
 s = find_dnode(t);
 if( s != tail) // 찾았다면
 {
  i = (dnode*)malloc(sizeof(dnode));
  i->key = k;
  s->prev->next = i; // s 의 prev 노드의 next 는 i 노드
  i->prev = s->prev; // i 의 prev 노드는 s 의 prev 노드
  s->prev = i;  // s 의 prev 노드는 i 노드
  i->next = s;  // i 의 next 노드는 s 노드
 }
 return i;
}

/************************************************************************/
/* 함수명 : ordered_insert                                              */
/* 임의의 순서로 입력되는 정수들을 오름차순으로 삽입     */
/************************************************************************/
dnode *ordered_insert(int k)
{
 dnode *s;
 dnode *i;
 s = head->next;
 while(s->key <= k && s != tail) // 삽입될 자리를 찾음
  s = s->next;
 i = (dnode*)malloc(sizeof(dnode));
 i->key = k;
 s->prev->next = i;
 i->prev = s->prev;
 s->prev = i;
 i->next = s;
 return i;
}

/************************************************************************/
/* 함수명 : print_dlist                                                 */
/* 리스트를 출력한다.             */
/************************************************************************/
void print_dlist(dnode *p)
{
 printf("\n");
 while(p != tail)
 {
  printf("%-8d", p->key);
  p = p->next;
 }
}

/************************************************************************/
/* 함수명 : delete_all                                                  */
/* 모든 노드를 삭제한다.            */
/************************************************************************/
void delete_all( void )
{
 dnode *p;
 dnode *s;
 p = head->next;
 while(p != tail)
 {
  s = p;
  p = p->next;
  free(s);
 }
 head->next = tail;
 tail->prev = head;
}

/************************************************************************/
/* 함수명 : main                                                        */
/* main function              */
/************************************************************************/
void main( void )
{
 dnode *t;
 init_dlist();
 
 ordered_insert(1);
 ordered_insert(2);
 ordered_insert(5);
 ordered_insert(6);
 
 ordered_insert(8);
 ordered_insert(9);
 ordered_insert(10);
 ordered_insert(11);
 ordered_insert(12);

 printf("\n Initial Linked list is ");
 print_dlist(head->next);

 printf("\n Finding 6 is %ssuccessful", find_dnode(6) == tail ? "un" : "");

 t = find_dnode(5);
 printf("\n Finding 5 is %ssuccessful", t == tail ? "un" : "");

 printf("\n Inserting 7 before 6");
 insert_dnode_ptr(7, t);
 print_dlist(head->next);

 t = find_dnode(3);
 printf("\n Deleting 10");
 delete_dnode_ptr(t);
 print_dlist(head->next);

 printf("\n Inserting node 2 before 5");
 insert_dnode(2, 10);
 print_dlist(head->next);

 printf("\n Deleting node 2");
 if(!delete_dnode(2))
  printf("\n deleting 2 is unsuccessful");
 print_dlist(head->next);

 printf("\n Deleting node 1");
 delete_dnode(1);
 print_dlist(head->next);

 printf("\n Inserting 15 at first");
 insert_dnode_ptr(15, head->next);
 print_dlist(head->next);
 
 printf("\n Deleting all node");
 delete_all();
 print_dlist(head->next);
 
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요