/*

双向循环链表

    1：双向循环链表创建

    2：双向循环链表长度

    3：双向循环链表正向遍历

    4：双向循环链表反向遍历

    5：双向循环链表节点插入

    6：双向循环链表节点删除

    7：双向循环链表倒序

    8：双向循环链表判空

    9：双向循环链表排序

    10：双向循环链表销毁

*/

#include <iostream>

using namespace std;

typedef struct node{

    struct node *pFront;

    int value;

    struct node *pNext;

}DCList;

/*创建双向循环链表*/

void Create(DCList* &Head,DCList* &End,int &nodecount )

{

    if(nodecount <=0)  return ;

    DCList *node = NULL;

    int nodevalue = 0;

    for(int i=0;i<nodecount;i++){

        cin>>nodevalue;

        node = new DCList;

        node->value = nodevalue;

        node->pFront = node;

        node->pNext = node;

        if(Head == NULL){

            Head = node;

        }

        else{

            node->pNext = Head;

            End->pNext = node;

            node->pNext->pFront = node;

            node->pFront = End;

        }

        End = node;

    }

}

/*获取双向链表的长度*/

void Length(DCList* &Head,DCList* &End,int &length)

{

    length = 1;

    DCList* ptr= Head;

    while(ptr != End){

        length++;

        ptr = ptr->pNext;

    }

}

/*双向链表正向遍历*/

void Traval(DCList* &Head,DCList* &End)

{

    if(Head == NULL || End == NULL)  return ;

    DCList *ptr = Head;

    while(ptr != End){

        cout<<ptr->value<<" ";

        ptr= ptr->pNext;

    }

    cout<<End->value<<endl;

}

/*双线循环链表的反向遍历*/

void ReTraval(DCList* &Head,DCList* &End){

    if(Head == NULL || End == NULL)  return ;

    DCList * ptr= End;

    while(ptr != Head){

        cout<<ptr->value<<" ";

        ptr=ptr->pFront;

    }

    cout<<Head->value<<endl;

}

/*双向循环链表节点插入*/

void Insert(DCList* &Head,DCList* &End,int &InsertPos,int InsertValue)

{

    if((Head == NULL || End == NULL) && InsertPos != 1)  return ;

    int length =0 ;

    Length(Head,End,length);

    if(InsertPos <=0 && InsertPos > length+1)  return ;

    DCList *insertnode = NULL;

    insertnode = new DCList;

    insertnode->value = InsertValue;

    int insertpos =1;

    DCList* insertfront = End;

    DCList* insertnext = Head;

    while(insertpos != InsertPos){

        insertfront = insertfront->pNext;

        insertnext =  insertfront->pNext;

        insertpos++;

    }

    insertnode->pNext = insertnext;

    insertnode->pNext->pFront = insertnode;

    insertfront->pNext = insertnode;

    insertfront->pNext->pFront = insertfront;

    if(InsertPos == 1){

        Head = insertnode;

    }

    else if(InsertPos == length+1){

        End = insertnode;

    }

}

/*双向循环链表节点删除*/

void Del(DCList* &Head,DCList* &End,int &DelPos)

{

    if(Head == NULL || End == NULL)  return ;

    int length =0;

    Length(Head,End,length);

    if(DelPos <= 0 || DelPos > length) return ;

    DCList * delfront = End;

    DCList * delnext =Head->pNext;

    int delpos = 1;

    while(delpos != DelPos){

        delfront = delfront->pNext;

        delnext = delnext->pNext;

        delpos++;

    }

    DCList *ptr = delfront->pNext;

    delfront->pNext = delnext;

    delnext->pFront = delfront;

    delete ptr ;

    ptr = NULL;

    if(DelPos == 1){

        Head = delnext;

    }

    else if(DelPos == length){

        End = delfront;

    }

}

/*双向循环链表倒序*/

void Reverse(DCList* &Head, DCList* &End)

{

    if(Head == NULL || End == NULL)  return ;

    DCList* Head_New = NULL;

    DCList* End_New = NULL;

    DCList *ptr = End;

    DCList *ptr_front = NULL;

    while(ptr != Head){

        ptr_front = ptr->pFront ;

        ptr->pFront = ptr;

        ptr->pNext = ptr;

        if(Head_New == NULL){

            Head_New = ptr;

        }

        else{

            ptr->pNext = Head_New;

            End_New->pNext = ptr;

            ptr->pNext->pFront = ptr;

            ptr->pFront = End_New;

        }

        End_New = ptr;

        ptr = ptr_front;

    }

    Head->pNext = Head_New;

    Head->pFront = End_New;

    Head_New->pFront = Head;

    End_New->pNext = Head;

    End_New = Head;

    Head = Head_New;

    End = End_New;

}

/*双向循环链表排序*/

void Sort(DCList* &Head,DCList* &End)

{

    if(Head == NULL || End == NULL)  return ;

    DCList *node = NULL;

    DCList* node_next = NULL;

    DCList* node_front = NULL;

    DCList* tmp = NULL;

    int length = 0;

    Length(Head,End,length);

    int nflag =0;

    for(int i=0;i<length;i++){

        nflag = 0;

        node = Head;

        node_next = node->pNext;

        node_front = Head;

        for(int j=0;j<length-i-1;j++){

            if(node->value > node_next->value){

                node->pNext = node_next->pNext;

                node->pNext->pFront = node;

                node_next->pNext = node;

                node_next->pNext->pFront = node_next;

                if(node != Head){

                    node_front->pNext = node_next;    

                    node_next->pFront = node_front;

                }

                if(node == Head){

                    Head = node_next;

                    node_next->pFront = NULL;

                }

                if(node_next == End){

                    End = node;

                }

                tmp = node;

                node = node_next;

                node_next = tmp;

                nflag = j+1;

            }

            node_front = node;

            node = node->pNext;

            node_next = node->pNext;

        }

        if(nflag == 0){

            break;

        }

        i = length-nflag-1;

    }

}

/*双向链表销毁*/

void Destroy(DCList* &Head,DCList* &End){

    if(Head == NULL || End == NULL)        return ;

    DCList * ptr = Head;

    DCList* ptr_next = NULL;

    while(ptr != End){

        ptr_next = ptr->pNext;

        delete ptr ;

        ptr = NULL;

        ptr = ptr_next;

    }

    delete End ;

    End = NULL;

    Head = NULL;

}

/*双向链表判空*/

bool m_is_empty(DCList* &Head,DCList* &End)

{

    if(Head == NULL || End == NULL)  

        return true;

    else 

        return false;

}

int main(){

    int length,nodecount,insertpos,insertvalue,delpos;

    DCList *Head = NULL ,*End = NULL;

    /*创建双循环链表*/

    cin>> nodecount;

    Create(Head,End,nodecount);

    Traval(Head,End);

    ReTraval(Head,End);

    Length(Head,End,length);

    cout<<length<<endl;

    //cout<<End->pNext->value<<" "<<Head->pFront->value<<endl;

    /*双向循环链表节点插入*/

    cin>> insertpos >> insertvalue;

    Insert(Head,End,insertpos,insertvalue);

    Traval(Head,End);

    ReTraval(Head,End);

    Length(Head,End,length);

    cout<<length<<endl;

    /*双向循环链表节点删除*/

    cin>> delpos ;

    Del(Head,End,delpos);

    Traval(Head,End);

    ReTraval(Head,End);

    Length(Head,End,length);

    cout<<length<<endl;

    /*双向链表倒序*/

    Reverse(Head,End);

    Traval(Head,End);

    ReTraval(Head,End);

    Length(Head,End,length);

    cout<<length<<endl;

    /*双向循环链表排序*/

    Sort(Head,End);

    Traval(Head,End);

    ReTraval(Head,End);

    Length(Head,End,length);

    cout<<length<<endl;

    /*双向循环链表判空*/

    bool m_empty = m_is_empty(Head,End);

    if(m_empty ){

        cout<<"is_empty"<<endl;

    }

    else{

        cout<<"is_not_empty"<<endl;

    }

    Destroy(Head,End);

    m_empty = m_is_empty(Head,End);

    if(m_empty ){

        cout<<"is_empty"<<endl;

    }

    else{

        cout<<"is_not_empty"<<endl;

    }

    system("pause");

    return 0;

}

实现双向循环链表的创建新节点，初始化，销毁，增加，删除，查找，求长度以及判空等基本操作。

头文件 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;

//双向循环带头链表
typedef struct ListNode
{
	struct ListNode* _next;  //后继
	struct ListNode* _prev;  //前驱
	LTDataType _data;   //数据域
}ListNode;
typedef struct List
{
	struct ListNode* _head;
	struct ListNode* _tail;
	int _size;
}List;
void ListInit(List* lt);
void ListDestory(List* lt);
void ListPushBack(List* lt, LTDataType x);
void ListPushFront(List* lt, LTDataType x);
void ListPopBack(List* lt,ListNode* pos,LTDataType x);
void ListPopFront(List* lt, ListNode* pos, LTDataType x);
ListNode* BuyListNode(LTDataType x);
ListNode* ListFind(List* lt, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(List* lt,ListNode* pos,LTDataType x);
int ListSize(List* lt);
int ListEmpty(List* lt);
void ListPrint(List* lt);
void testListNode();

 

test.c

1.创建新节点

#include "List.h"
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode != NULL)
	{
		newnode->_data = x;
		newnode ->_prev = NULL;
		newnode->_next = NULL;
	}
	return newnode;
}

2.链表初始化

void ListInit(List* lt)
{
	assert(lt != NULL);
	lt->_head= BuyListNode(0);
	lt->_head->_next = lt->_head;
	lt->_head->_prev = lt->_head;
}

3.链表销毁

void ListDestory(List* lt)
{
	ListNode* cur = NULL;
	ListNode* tail=NULL;
	assert(lt!= NULL);
		cur = lt;
		while (cur!=tail)
		{
			ListNode* del = cur;
			cur = cur->_next;
			free(del);
			del = NULL;
		}
		free(cur);
}

4.在链表中插入数据 注：因为是双向循环链表在任何地方插入都是一样的实现。

void ListInsert(ListNode* pos, LTDataType x) //pos之前插入  prev newnode pos
{
	assert(pos != NULL);
	ListNode* newnode;
	newnode = BuyListNode(3);
	newnode->_data = x;
	ListNode* prev = pos->_prev;
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = pos;
	pos->_prev = newnode;
}
void ListPushBack(List* lt, LTDataType x)// tail newnode head
{
	ListInsert(lt->_head, x);
}
void ListPushFront(List* lt, LTDataType x) // tail newnode head
{
	ListInsert(lt->_head, x);
}

5.查找链表中指定位置元素

ListNode* ListFind(List* lt, LTDataType x)
{
	int i = 0;
	while (lt != NULL && lt->_head->_data != x)//寻找值为x的元素**注意这里循环的条件不能写反。原因，当L == NULL 时候 L->data会出错
	{
		i++;
		lt = lt->_head->_next;
	}
	if (lt == NULL)               //如果没找到返回-1
		return -1;
	else
		return x;
}

6.删除指定位置元素

void ListErase(List* lt,ListNode* pos,LTDataType x)
{
	if (lt == NULL && pos < 1)
	{
		return;
	}
	if (pos>ListSize(lt))
	{
		return;
	}
	ListNode *pNode = lt;
	int count = 0;
	while (count < ListSize(lt))
	{
		pNode = pNode->_next;
		count++;
	}
	if (count != pos)
		return;
	x = pNode->_data;
	pNode->_prev->_next = pNode->_next;
	pNode->_next->_prev = pNode->_prev;
	free(pNode);
	pNode = NULL;

}
void ListPopBack(List* lt, ListNode* pos, LTDataType x) // tail head
{
	assert(lt != NULL);
	ListErase(lt->_head, pos, x);
}
void ListPopFront(List* lt, ListNode* pos, LTDataType x)
{
	assert(lt != NULL);
	ListErase(lt->_head, pos, x);
}

7.求链表长度

int ListSize(List* lt)
{
	int size = 0;
	assert(lt != NULL);
	if (lt->_head!=lt->_head->_prev)
	{
		++size;
		lt->_head = lt->_head->_next;
	}
	return size;
}

9.判断链表是否为空

int ListEmpty(List* lt)
{
	if (ListSize(lt) == 0 && lt->_head->_next == lt->_head->_prev)
		return 1;
	else
		return 0;
}

10.打印链表

void ListPrint(List* lt)
{
	ListNode* cur = lt->_head->_next;
	while (cur != lt->_head)
	{
		printf("%d ", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}

主函数

void testListNode()
{
	ListNode* s;
	ListInit(&s);
	ListPushBack(&s, 1);
	ListPushBack(&s, 2);
	ListPushBack(&s, 3);
	ListPushBack(&s, 4);
	ListPrint(&s);
	int ret = ListFind(&s, 3);
	if (ret != -1)
	{
		printf("%d ", ret);
	}
	else
	{
		printf("找不到");
	}
	printf("\n");
	int size=ListSize(&s);
	printf("%d ", size);
	printf("\n");
	int n = ListEmpty(&s);
	printf("%d ", n);
}
int main()
{
	testListNode();
	system("pause");
	return;
}

 

双向循环链表
一、双向循环链表
0.头文件
1. 判空
2. 申请新结点
3. 初始化
4.获取长度
5.插入
1.按位置插
2.头插
3.尾插
6.打印
1.正向打印
2.逆向打印
7.删除
1.按位置删除
2.头删
3.尾删
8.主函数

一、双向循环链表
0.头文件
#pragma once

typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* prior;
	struct Node* next;
}CDLNode,*CDLinkList;

void InitCDLinkList(CDLinkList list);

int InsertCDLinkListPos(CDLinkList list, ElemType val, int pos);
int InsertCDLinkListHead(CDLinkList list, ElemType val);
int InsertCDLinkListTail(CDLinkList list, ElemType val);

void ShowCDLinkList(CDLinkList list);
void RShowCDLinkList(CDLinkList list);


int DeleteCDLinkListPos(CDLinkList list, int pos);
int DeleteCDLinkListHead(CDLinkList list);
int DeleteCDLinkListTail(CDLinkList list);


1. 判空
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"cdlist.h"

void DeterPointIsNull(CDLinkList list)
{
	assert(list != NULL);
	if (list == NULL)
	{
		exit(0);
	}
}

2. 申请新结点
static CDLinkList ApplyNode(ElemType val, CDLinkList prior, CDLinkList next)
{
	CDLinkList p = (CDLinkList)malloc(sizeof(CDLNode));
	assert(p != NULL);
	p->data = val;
	p->prior = prior;
	p->next = next;
	return p;
}

3. 初始化
void InitCDLinkList(CDLinkList list)
{
	DeterPointIsNull(list);
	list->prior = list->next=list;
}

4.获取长度
int GetLen(CDLinkList list)
{
	DeterPointIsNull(list);
	int len = 0;
	CDLinkList p = list->next;
	while (p != list)  //现在是循环链表  条件是p不等于头结点
	{
		len++;
		p = p->next;
	}
	return len;
}

5.插入
1.按位置插
//可以考虑pos和长度一半比较   考虑从前往后跑还是从后往前跑
int InsertCDLinkListPos(CDLinkList list, ElemType val, int pos)
{
	DeterPointIsNull(list);
	if (pos<0 || pos>GetLen(list))
	{
		printf("Pos is error,Insert Fail\n");
		return 0;
	}
	CDLinkList p = list;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	p->next->prior = ApplyNode(val, p, p->next);
	p->next= ApplyNode(val,p,p->next);
	return 1;
}


2.头插
//O(1)
int InsertCDLinkListHead(CDLinkList list, ElemType val)
{
	DeterPointIsNull(list);
	return InsertCDLinkListPos(list,val, 0);
}

3.尾插
//O(1)
int InsertCDLinkListTail(CDLinkList list, ElemType val)
{
	DeterPointIsNull(list);
	
	//return InsertCDLinkListPos(list, val,GetLen(list));
	//如果进行转调，反而会降低效率，提高时间复杂度，因为需要从头找到尾

	CDLinkList p = list->prior;//p就是最后一个节点
	p->next->prior = ApplyNode(val, p, p->next);
	p->next = ApplyNode(val, p, p->next);
	return 1;
}

6.打印
1.正向打印
void ShowCDLinkList(CDLinkList list)
{
	DeterPointIsNull(list);
	CDLinkList p = list->next;
	while (p != list)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

2.逆向打印
void RShowCDLinkList(CDLinkList list)
{
	DeterPointIsNull(list);
	CDLinkList p = list->prior;
	while (p != list)
	{
		printf("%d ", p->data);
		p = p->prior;
	}
	printf("\n");
}


7.删除
1.按位置删除
int DeleteCDLinkListPos(CDLinkList list, int pos)
{
	DeterPointIsNull(list);
	if (pos < 0 || pos >= GetLen(list))
	{
		printf("Pos is error,Delete Fail\n");
		return 0;
	}
	CDLinkList p = list;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	CDLinkList s = p->next;
	p->next = s->next;
	s->next->prior = p;
	free(s);
	return 1;
}

2.头删
int DeleteCDLinkListHead(CDLinkList list)
{
	DeterPointIsNull(list);
	return DeleteCDLinkListPos(list, 0);
}

3.尾删
int DeleteCDLinkListTail(CDLinkList list)
{
	DeterPointIsNull(list);
	CDLinkList p = list->prior;
	list->prior = p->prior;
	p->prior->next = list;

	free(p);
	return 1;
}

8.主函数
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"cdlist.h"

int main()
{

	return 0;
}

对于单链表来说，每个结点都有一个引用域，即next域，用来指向下一个结点，即该结点的后继结点，因此链表中的最后一个节点的引用域必定为空，单链表的这种存储方式决定了它的访问方式，只能从单链表的表头进行遍历。而双向循环链表是由双向链表和循环链表组合而成的，双向链中的数据结构中有三个域，前驱指针域，数据域，后继指针域。而循环链表的尾指针指向头指针。双向循环链表具有以下特点：
(1) 判空条件：head.next==head为空。
(2)双向循环链表的head指针的prior指向最后一个结点，而next指向第一个结点。而尾结点的next域指向头指针head.
双向循环链表的实现类，有结点类和链表类。
下面是双向循环链表的java实现：
 
Dlnode结点类:
 
/**

 * Dlnode用来定义双向循环链表 双向循环链表应该包括一个数据域，一个前驱域和一个数据域 最后一个节点指向第一个首节点
 * 
 * @author Administrator
 * 
 */
public class Dlnode {
 Object data;// 数据域
 Dlnode prior;// 指向前驱的指针域
 Dlnode next;// 指向后继的指针域
 public Dlnode(Dlnode prior, Object data, Dlnode next) {
  this.prior = prior;
  this.data = data;
  this.next = next;
 }
 public Dlnode() {
  this(null, null, null);
 }
 public Object getData() {
  return data;
 }
 public void setData(Object data) {
  this.data = data;
 }
 public Dlnode getNext() {
  return next;
 }
 public void setNext(Dlnode next) {
  this.next = next;
 }
 public Dlnode getPrior() {
  return prior;
 }
 public void setPrior(Dlnode prior) {
  this.prior = prior;
 }
}
 
 链表类的实现：
 /**
 * 此类是实现双向循环链表 双向循环链表的特点: (1)空结点：只有一个首结点，其前驱与后继都指向自身。 (2)非空：后一个结点的前驱指向前一个节点
 * 前一个节点的后继指向后一个节点 最后一个节点的后继指向首节点 首节点的前驱指向最后一个节点
 * 
 * @author Administrator
 * 
 */
public class DlList {
 Dlnode dlhead;// 链表表头
 int size;
 public DlList() {
  dlhead = new Dlnode();
  dlhead.prior = dlhead;
  dlhead.next = dlhead;
  size = 0;
 }// 构造一个空表
 public DlList(Object[] a) {// 用数组a构造一个双向循环链表
  dlhead = new Dlnode();
  dlhead.prior = dlhead;
  dlhead.next = dlhead;
  Dlnode p = null;
  for (int i = a.length - 1; i >= 0; i--) {
   p = new Dlnode(dlhead, a[i], dlhead.next);
   dlhead.next.setPrior(p);
   dlhead.setNext(p);
  }
  size = a.length;
 }
 public void clear() {
  dlhead = new Dlnode();
  dlhead.prior = dlhead;
  dlhead.next = dlhead;
 }
 /**
  * 找到双向循环链表中第i个节点 首节点是第0个节点，然后 是第1个节点，依次类推
  * 
  * @param i
  * @return
  */
 public Dlnode index(int i) {
  Dlnode p;
  int j;
  if (i < 0 || i > size)
   p = null;
  else if (i == 0)
   p = dlhead;
  else {
   p = dlhead.next;
   j = 1;
   while (j < i && p != null) {
    p = p.next;
    j++;
   }
  }
  return p;
 }
 /**
  * 得到第i个节点的data值
  * 
  * @param i
  * @return
  */
 public Object get(int i) {
  Dlnode p;
  if (i <= 0 || i > size)
   return null;
  else {
   p = index(i);
   return p.getData();
  }
 }
 /**
  * 计算双向循环链表的长度
  * 
  */
 public int len() {
  return size;
 }
 /**
  * 得到data域为el的节点索引号
  * 
  * @param el
  * @return
  */
 public int loc(Object el) {
  Dlnode p;
  int j = 1;
  p = dlhead.next;
  while (!p.data.equals(el) && p != dlhead) {// 双向循环链表结束的条件是尾结点的下一个指针是否指向头结点
   j++;
   p = p.next;
  }
  if (p != dlhead)
   return j;
  else
   return 0;
 }
 /**
  * 第一个参数是插入的位置 第二个参数是插入节点的data值
  * 
  * @param loc
  * @param el
  * @return
  */
 public boolean insert(int loc, Object el) {
  if (loc < 1 && loc > size + 1)
   return false;
  Dlnode p = index(loc - 1);
  Dlnode q = new Dlnode(p, el, p.next);
  p.next.setPrior(q);
  p.setNext(q);
  size++;
  return true;
 }
 /**
  * 删除结点，提供删除节点的索引号
  * 
  */
 public Object delete(int i) {
  if (size == 0 || i < 1 || i > size)
   return null;
  Dlnode p = index(i);
  Object data = p.getData();
  p.prior.setNext(p.next);
  p.next.setPrior(p.prior);
  size--;
  return data;
 }
 public boolean empty() {
  return dlhead.next == dlhead;
 }
}
 
 
 测试类：
 
public class TestDllist {
 /**
  * @param args
  */
 public static void main(String[] args) {
  DlList dl = new DlList();
  for (int i = 0; i < 10; i++)
   dl.insert((i + 1), new Integer(i + 1));
  print(dl);
 }
 public static void print(DlList dl) {
  System.out.println("双向循环链表遍历结果:");
  Dlnode p;
  p = dl.dlhead.next;
  while (p != dl.dlhead) {
   System.out.print(p.getData() + " ");
   p = p.next;
  }
 }
}
 双向循环链表插入与删除时间复杂度的分析：
双向循环链表的插入与删除的时间复杂度都为O(1).由于删除时寻找前驱结点只需要p->prior即可。