// ConsoleApplication8.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
struct Node
{
    int Value;
    Node * Next;
    Node * Prev;
};
typedef struct Node Node;
Node * Create(int value)
{
    Node * t = (Node *)malloc(sizeof(Node));
    t->Value = value;
    t->Next = t;
    t->Prev = t;
    return(t);
}
Node * GetTail(Node * root)
{
    Node * tmp = root;
    while(tmp->Next != root)
    {
        tmp = tmp->Next;
    }
    return(tmp);
}
void Add(Node * root, int value)
{
    Node * t = (Node *)malloc(sizeof(Node));
    t->Value = value;
    Node * tmp = GetTail(root);
    tmp->Next = t;
    t->Next = root;
    t->Prev = tmp;
    Node * r = root;
    root->Prev = t;
}
Node * Find(Node * root, int value)
{
    Node * t = root;
    while(t->Next != root)
    {
        if(t->Value == value)
        {
            return(t);
        }
        t = t->Next;
    }
    if(t->Value == value)
        return(t);
    return(NULL);
}
void Free(Node * t)
{
    free(t);
}
Node * Remove(Node * root, int value)
{
    Node * tmp = GetTail(root);
    Node * t = Find(root, value);
    Node * prev = t->Prev;
    Node * next = t->Next;
    if(t == tmp)
    {
        prev->Next = root;
        root->Prev = prev;
    }
    else if(t == root)
    {
        root = next;
        tmp->Next = root;
        root->Prev = tmp;
    }
    else
    {
        prev->Next = t->Next;
        next->Prev = t->Prev;
    }
    Free(t);
    return(root);
}
void List(Node * root)
{
    Node * t = root;
    while(t->Next != root)
    {
        printf("%d ", t->Value);
        t = t->Next;
    }
    printf("%d\r\n", t->Value);
}
int _tmain(int argc, _TCHAR* argv[])
{
    Node * root;
    root = Create(1);
    Add(root, 2);
    Add(root, 3);
    Add(root, 4);
    Add(root, 5);
    List(root);
    Node * find = Find(root, 3);
    printf("%d\r\n", find);
    root = Remove(root, 3);
    root = Remove(root, 1);
    root = Remove(root, 5);
    List(root);
    Free(root);
    return 0;
}