一、单向循环链表

• 单向循环链表：
  如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的下一跳指向头结点。

单向循环链表 –多个节点

单向循环链表 – 只有1个节点

对于和我们之前学的单向链表相比，单向循环链表的区别在于其尾节点指向链表的首节点，我们在单链表（Linked List）的clear、add、remove、indexOf以及toString方法的底层封装的博客上面可以改动的也无非就是添加和删除的操作。

（一）单向循环链表 — add(int index, E element)

@Override
public void add(int index, E element) {
	rangeCheckForAdd(index);
	
	if (index == 0) {
		//先不要修改first，因为要是修改了；再找最后一个节点的时候会发生变化
		Node<E> newFirst = new Node<>(element, first);
		// 拿到最后一个节点
		Node<E> last = (size == 0) ? newFirst : node(size - 1);
		last.next = newFirst;
		first = newFirst;
	} else {
		Node<E> prev = node(index - 1);
		prev.next = new Node<>(element, prev.next);
	}
	size++;
}

（二）单向循环链表 — remove(int index)

@Override
public E remove(int index) {
	rangeCheck(index);
	
	Node<E> node = first;
	if (index == 0) {
		if (size == 1) {
			first = null;
		} else {
			//先拿到最后一个节点
			Node<E> last = node(size - 1);
			//再改变first节点
			first = first.next;
			last.next = first;
		}
	} else {
		Node<E> prev = node(index - 1);
		node = prev.next;
		prev.next = node.next;
	}
	size--;
	return node.element;
}

（三）单向循环链表 — node中的toString方法

private static class Node<E> {
	E element;
	Node<E> next;
	public Node(E element, Node<E> next) {
		this.element = element;
		this.next = next;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(element).append("_").append(next.element);
		return sb.toString();
	}
}

（四）测试

import com.mj.circle.SingleCircleLinkedList;
public class Main {
	static void testList(List<Integer> list) {
		list.add(11);
		list.add(22);
		list.add(33);
		list.add(44);

		list.add(0, 55); // [55, 11, 22, 33, 44]
		list.add(2, 66); // [55, 11, 66, 22, 33, 44]
		list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

		list.remove(0); // [11, 66, 22, 33, 44, 77]
		list.remove(2); // [11, 66, 33, 44, 77]
		list.remove(list.size() - 1); // [11, 66, 33, 44]		
		System.out.println(list);
	}
	public static void main(String[] args) {
		 testList(new SingleCircleLinkedList<>());	
	}
}
运行结果：
size=4, [11_66, 66_33, 33_44, 44_11]

二、双向循环链表

双向循环链表 –多个节点

双向循环链表 – 只有1个节点

• 双向循环链表：双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

（一）单向循环链表 — add(int index, E element)

@Override
public void add(int index, E element) {
	rangeCheckForAdd(index);

	// size == 0
	// index == 0
	if (index == size) { // 往最后面添加元素
		Node<E> oldLast = last;
		last = new Node<>(oldLast, element, first);
		if (oldLast == null) { // 这是链表添加的第一个元素
			first = last;
			first.next = first;
			first.prev = first;
		} else {
			oldLast.next = last;
			first.prev = last;
		}
	} else {
		Node<E> next = node(index); 
		Node<E> prev = next.prev; 
		Node<E> node = new Node<>(prev, element, next);
		next.prev = node;
		prev.next = node;
		
		if (next == first) { // index == 0
			first = node;
		}
	}
	
	size++;
}

（二）单向循环链表 — remove(int index)

@Override
public E remove(int index) {
	rangeCheck(index);
	return remove(node(index));
}

private E remove(Node<E> node) {
	if (size == 1) {
		first = null;
		last = null;
	} else {
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		prev.next = next;
		next.prev = prev;
		
		if (node == first) { // index == 0
			first = next;
		}
		
		if (node == last) { // index == size - 1
			last = prev;
		}
	}
	
	size--;
	return node.element;
}

（三）单向循环链表 — node中的toString方法

private static class Node<E> {
E element;
	Node<E> prev;
	Node<E> next;
	public Node(Node<E> prev, E element, Node<E> next) {
		this.prev = prev;
		this.element = element;
		this.next = next;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		
		if (prev != null) {
			sb.append(prev.element);
		} else {
			sb.append("null");
		}
		
		sb.append("_").append(element).append("_");

		if (next != null) {
			sb.append(next.element);
		} else {
			sb.append("null");
		}
		
		return sb.toString();
	}
}

（四）测试

import com.mj.circle.CircleLinkedList;
public class Main {
	static void testList(List<Integer> list) {
		list.add(11);
		list.add(22);
		list.add(33);
		list.add(44);

		list.add(0, 55); // [55, 11, 22, 33, 44]
		list.add(2, 66); // [55, 11, 66, 22, 33, 44]
		list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

		list.remove(0); // [11, 66, 22, 33, 44, 77]
		list.remove(2); // [11, 66, 33, 44, 77]
		list.remove(list.size() - 1); // [11, 66, 33, 44]
		
		System.out.println(list);
	}

	public static void main(String[] args) {
		 testList(new CircleLinkedList<>());
	}
}
运行结果：
size=4, [44_11_66, 11_66_33, 66_33_44, 33_44_11]

带尾结点指针的单循环链表结构

//带尾结点的单循环链表
//可以不要头指针

typedef int elementType;
typedef struct LinkedList{
	elementType data;
	struct LinkedList* next;
}node;

带尾结点指针的单循环链表初始化

//R是尾结点 
void initialList(node *&R){
	R = new node;//申请头结点 
	R->next = R; 
} 

求表长度

//求表长度
int listLength(node* R){
	int len = 0;
	node* p = R->next->next;//指向表中的第一个元素 
	
	//当p指针没有指向头结点时继续循环 
	while (p != R->next){
		len++;
		p = p->next;
	}
	
	return len;
} 

插入操作

//插入操作 
int listInsert(node *R, int i, elementType x){
	node* p, *S;
	int k = 0;
	//指向头结点 
	p = R->next;
	
	//找到要插入位置的前一个结点 
	while (k != i-1 && p->next != R->next){
		k++;
		p = p->next;
	} 
	
	//i超出范围 
	if (k != i-1){
		return false;
	}
	else{
		S = new node;
		S->data = x;
		S->next = p->next;
		p->next = S;
		//如果插入的位置在尾结点之后，则修改尾结点的指向 
		if (R->next == S)
			R = S;
			
		return true;
	}
}

删除操作

//删除操作 
bool listDelete(node *&R, int i, elementType &x){
	node* p = R->next;
	node* u;
	int k = 0;
	//找到要删除结点的前一个结点 
	while (k != i-1 && p->next != R->next){
		k++;
		p = p->next;
	}
	//如果p指向尾结点，则i超出范围 
	if (p->next == R->next)
		return false; //i超出范围
	else{
		u = p->next;
		p = u->next;
		x = u->data;
		
		//如果删除的是尾结点，则修改尾结点指针的指向 
		if (R == u)
			u = p;
			
		delete u;
		
		return true;
	} 
}

将A、B两个带尾指针的单循环链表首 尾相接，尽量节省时间

void scrMergeAB(node *&A, node *&B){
	node* u;
	
	u = A->next;//保留A的头结点的位置 
	A->next = B->next->next;//将A的尾结点指针指向B的第一个结点 
	delete B->next;//删除B的头结点 
	B->next = u;//将B的尾结点的next指针指向A的头结点 
	
	A = B;//A和B指针都指向新链表的尾结点 
} 

单向循环链表

循环链表和单链表的区别

1. 表中最后结点的指针不是NULL，而是改为指向头结点，从而整个链表形成了一个环。

2. 循环单链表中没有指针域为NULL的结点，故判空条件为判断 *A （表尾节点） *A 的next是否为头指针

3. 空表：if(A->next == H) { 空表 }

循环链表的特点

• 循环单链表插入，删除算法于单链表几乎一样

正是因为循环单链表是一个“环”，在任何位置插入和删除操作都是等价的，无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表，循环链表不设头指针而仅设尾指针，若只设置尾指针A，A->next即为头指针，对表头，表尾进行操作都只要O(n).

• 关于两个循环链表合并为一个循环链表
  

双向循环链表——概念

在单链表L中，查找ai的后继Next(L，a;)，耗时仅为O(1)，因为取ai后继指针即可。
但查找ai的直接前驱Prior(L，ai);则需从链表的头指针开始，找到结点ai前一结点即是。故运算Prior(L，ai)依赖表长n，耗时为O(n)。另外，若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足

为此，引入双向链表。先定义双向链表中的结点:

其中，data和next同单链表，增加一指针域prior，其指向本结点的直接前驱。
结点描述:

typedef int data_t; 
typedef struct dnode_t
{ 
        data_tdata;
        struct dnode_t *prior;
        struct dnode_t *next;
}dlinknode_t , *dlinklist_t;

• 表L=(a0·····an-1)(设n=2) 的双向循环链表如图：
  
  设p为链表中某结点的指针，有对称性：

  (p->prior)->next = p =(p->next)->prior

• 双向链表的查找等运算基本上和单链表类似。
• 在双向循环链表中，某结点 *p 为尾结点时，p->next == H,当循环双链表尾空表时，某头结点的prior域和next域都等于H

下面我们学习一下双向循环链表的插入和删除运算

1. 双向循环链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

① q->prior = p->prior;
② (p->prior)->next = q;
③ q->next = p;
④ p->prior=q;

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
  此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);

2. 双向循环链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除

概念我们了解了，接下来我们要去实现双向链表的操作。

双向链表的插入创建

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;


extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
#endif

文件二：dlist.c 插入创建双向链表

#include"dlist.h"

//创建双向链表
dlistnode *dlist_create(){
   dlistnode *H,*p,*r;
   int num;

   if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
   }
   //建立空双向链表
   H->prior = H;   //头结点前驱后继都指向自己
   H->next = H;    
   r = H;          //指针r 指向头结点
   //用户输入
   while(1) {
       puts("please input(-1 exit):");
       scanf("%d",&num);
       if(num == -1){
	       puts("-1 exit");
	       break;
       }

       if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
       }
       //新节点赋值
       p->data = num;
       
       //插入双向链表
       p->prior = r;
       p->next = r->next;
       r->next = p;
       H->prior = p;
       r = p;

   } 
   return H;
}

//遍历链表并输出链表数据
void dlist_show(dlistnode *H){

   dlistnode *p;
   p = H->next;

   while(p != H){
       printf("%d ",p->data);
       p=p->next;
   }
   puts("");
}

文件三：test.c 插入创建双向链表

#include"dlist.h"


int main(){

   dlistnode *H;

   H=dlist_create();

   dlist_show(H);

   return 0;
}

双向链表——查找

查找：getlist(L,i);提供要查找结点ai的编号，返回指向该结点ai的指针

结点个数 n=3; i的范围【0，n-1】

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos)；
#endif

文件二：dlist.c 按位查找双向链表

dlistnode *dlist_get(dlistnode *H,int pos){
    int i =-1;
    dlistnode *p = H;

    if(pos < 0){
        puts("pos < 0,invalid");
        return NULL;
    }
    
    while(i < pos){
	   p = p->next;
	   i++;
	   if(p == H){
	       puts("pos is invalid");
	       return NULL;
	   }
    }
    return p;
}

文件三：test.c 用户输入按位查找双向链表

#include"dlist.h"


int main(){

   dlistnode *H,*p;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
   while(1){
      puts("input pos");
      scanf("%d",&pos);
      p =  dlist_get(H,pos);
      if(p){
         printf("%d \n",p->data);
      }
   }
   return 0;
}

双向链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
  此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
#endif

文件二：dlist.c 按位插入双向链表

int dlist_insert(dlistnode *H , int value ,int pos){
	dlistnode *p,*q;

	p = dlist_get(H,pos);
	if(p == NULL){
            return -1;
	}
        
        if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	   puts("malloc failed");
	   return -1;
        } 
	q->data = value;

	q->prior = p->prior;
	q->next = p;
	p->prior->next = q;
	q->prior = q;

	return 0;
}

文件三：test.c 用户输入按位插入双向链表

#include"dlist.h"


int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
     while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_insert(H,100,pos);
      dlist_show(H);
      }
   return 0;
}

双向链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

 p->prior->next = p->next;
 p->next->prior = p-prior;

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除
  文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
extern int dlist_delete(dlistnode *H ,int pos);
#endif

文件二：dlist.c 用户输入按位删除双向链表

int dlist_delete(dlistnode *H ,int pos){
    dlistnode *p;

    p = dlist_get(H,pos);
    if(p == NULL){
            return -1;
    }
    
    p->prior->next = p->next;
    p->next->prior = p-prior;

    free(p);
    p=NULL;
    return 0;
}

文件三：test.c 用户输入按位删除双向链表

#include"dlist.h"

int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);

    while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_delete(H,pos);
      dlist_show(H);
    }
   return 0;
}

-----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------

--------------------------------------------------------[下期预告：线性表的应用举例]------------------------------------------------------