이중연결리스트

//******************************************************************************

// 이중연결리스트 !!

//******************************************************************************

// 단일연결리스트 -> 단방향성

//*****************************5*************************************************

#include <stdio.h>

#include <malloc.h>

//******************************************************************************

// 구조체 선언

//******************************************************************************

typedef struct _Node

{

int data; // data

struct _Node * next; //다음 링크

struct _Node * prev; //이전 링크

}Node;

//******************************************************************************

//head , tail 더미 노드 활용 !!

//******************************************************************************

Node *head;

//******************************************************************************

// Utill

//******************************************************************************

Node *CreateNode(int data) //노드 생성

{

Node *Newnode = (Node *)malloc(sizeof(Node));

Newnode->data = data;

Newnode->next = NULL;

Newnode->prev = NULL;

return Newnode;

}

//******************************************************************************

void init()

{

head = CreateNode(0);

head->next = NULL;

head->prev = head;

}

//******************************************************************************

// 삽입연산 함수들

//******************************************************************************

void push_back(int data)

{

Node *Newnode = CreateNode(data);

Newnode->next = NULL;

tail->prev->next = Newnode;

Newnode->prev = tail->prev;

tail->prev = Newnode;

}

void push_front(int data)

{

Node * Newnode = CreateNode(data);

Newnode->prev = head;

head->next->prev = Newnode;

Newnode->next = head->next;

head->next = Newnode;

}

void insert(int key, int data)

{

Node *p = head->next;

Node *Newnode = CreateNode(data);

while(p != tail){

if(p->data == key){

Newnode->next = p->next;

Newnode->prev = p;

p->next->prev = Newnode;

p->next = Newnode;

return;

}

else{

p = p-> next;

}

}

Newnode->next = tail;

tail->prev->next = Newnode;

Newnode->prev = tail->prev;

tail->prev = Newnode;

}

//******************************************************************************

//삭제연산 함수들

//******************************************************************************

void pop_back()

{

Node *p = tail->prev;

if(tail->prev == head){

printf("list empty !!!");

}

else{

p->prev->next = tail;

tail->prev = p->prev;

free(p);

}

}

void pop_front()

{

Node *p = head->next;

if(head->next == tail){

printf("list empty");

}

else{

head->next = p->next;

free(p);

}

}

void erase(int key)

{

Node *p = head->next;

Node *s;

while(p != tail){

if(p->data == key){

p->prev->next = p->next;

p->next->prev = p->prev;

s = p->next;

free(p);

p = s;

//return;

}

else{

p = p-> next;

}

}

}

//******************************************************************************

void show()

{

Node *p = head->next;

while(p != tail)

{

printf("%d-->", p->data); 

p = p->next;

}

puts("");

}

void main()

{

init();

push_back(30);

show();

push_back(50);

show();

push_front(30);

show();

push_front(30);

show();

push_front(50);

show();

push_front(30);

show();

erase(30);

show();

}