Linked List (IN C)

************************************************************************************************************************

이중연결리스트

이중 연결 리스트(Doubly Linked List) 알고리즘을 이용한 예제입니다.

실제로 이중 연결 리스트는 많이 사용이 됩니다. 특히 활용이 많은 곳은 에디터나 워드프로세이며

여기서 이중 연결 리스트는 문장을 저장하는 가장 적절한 방법으로 간주됩니다.

왜냐하면 워드프로세서의 문장들은 그 크기가 자주 변하고, 재배치되는 경우도 비번하기 때문에

이중 연결 리스트를 사용할 경우 자료의 크기 변화나 재배치에 효율적입니다.

그리고 이중 연결 리스트는 앞 뒤 링크를 모두 가지고 있어 문장간의 이동도 용이합니다.

===============================================================

#include<stdio.h>
#include<stdlib.h>

typedef struct _dnode{
 int key;    //정보 저장
 struct _dnode *prev;  //앞 노드의 위치 저장
 struct _dnode *next;  //다음 노드의 위치 저장
} dnode;

dnode *head, *tail;   //전역 변수로 정의

void init_dlist(void)  //초기화 함수
{
 head=(dnode*)malloc(sizeof(dnode));  //head의 공간 확보
 tail=(dnode*)malloc(sizeof(dnode));  //tail의 공간 확보
 head->next=tail;
 head->prev=head;
 tail->next=tail;
 tail->prev=head;
}

dnode *find_dnode(int k)  //k값을 연결 리스트에서 찾아내는 함수
{
 dnode *s;
 s=head->next;
 while(s->key != k && s != tail)  //key를 찾거나 tail에 도달하면 끝
  s=s->next;
 return s;
}

int delete_dnode(int k)  //k값을 갖는 노드를 찾아서 삭제
{
 dnode *s; 
 s=find_dnode(k);
 if(s != tail)
 {
  s->prev->next=s->next;
  s->next->prev=s->prev;
  free(s);
  return 1;
 }
 return 0;
}

dnode *insert_dnode(int k, int t)  //t앞에 k를 삽입
{
 dnode *s; 
 dnode *i=NULL; 
 s=find_dnode(t);
 if(s != tail)
 {
  i=(dnode*)malloc(sizeof(dnode));
  i->key=k;
  s->prev->next=i;
  i->prev=s->prev;
  s->prev=i;
  i->next=s;
 }
 return i;
}

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;
}

int delete_dnode_ptr(dnode *p)  //p가 가리키는 노드를 삭제
{
 if(p==head || p==tail)
  return 0;
 p->prev->next=p->next;
 p->next->prev=p->prev;
 free(p);
 return 1;
}

dnode *insert_dnode_ptr(int k, dnode *t) //t노드 앞에 k값을 삽입
{
 dnode *i;
 if(t==head)
  return NULL;
 i=(dnode*)malloc(sizeof(dnode));
 i->key=k;
 t->prev->next=i;
 i->prev=t->prev;
 t->prev=i;
 i->next=t;
 return i;
}

void print_dlist(dnode* p)  //화면에 출력하는 함수
{
 printf("\n");
 while(p != tail)
 {
  printf("%-8d", p->key);
  p=p->next;
 }
}

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;
}

void main(void)
{
 dnode *t;
 init_dlist();

 ordered_insert(10);  //순서를 유지하면서 삽입
 ordered_insert(5);
 ordered_insert(8);
 ordered_insert(3);
 ordered_insert(1);
 ordered_insert(7);
 ordered_insert(8);

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

 printf("\nFinding 4 is %ssuccessful", find_dnode(4)==tail ? "un" : "");

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

 printf("\nInserting 7 before 5");
 insert_dnode_ptr(7, t);
 print_dlist(head->next);

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

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

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

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

 printf("\nInserting 15 at first");
 insert_dnode_ptr(15, head->next);
 print_dlist(head->next);

 printf("\nDeleting all node");
 delete_all();
 print_dlist(head->next);
}