关键词:
1.1 基本介绍
双向循环链表就是在双线链表的基础上首尾相连(第一个节点的prev指向最后一个节点,最后一个节点的next指向第一个节点)。
1.2 添加操作
1、思路分析
头部插入
当整个链表都为空时,添加操作。
头结点和尾节点都指向自己。
当链表不为空时,添加操作
先把当前头节点的上一跳地址给新元素的上一跳
然后让新节点的后驱指针指向head
结点,再让head
的前驱指针指向新元素。
更新head
结点,让head
结点指向新结点,更新tail
结点,让tail
的下一跳重新指向head
。
尾部插入
将当前tail
的下一跳给新节点的下一跳
让tail
的下一跳指向新结点,新结点的上一跳指向tail
。
tail
重新指向新结点。
直接让head
的上一跳重新指向tail
。
中间插入
1、离头部比较近
定义两个指针p
,q
,找到要插入节点前驱,让p
的上一跳指向新节点,让新节点的下一跳指向p
。
让q
的上一跳指向新节点,让新节点的下一跳指向q
。
2、离尾部比较近
让q
的下一跳指向新节点,让新节点的上一跳指向q
。
让p
的上一跳指向新节点,让新节点的下一跳指向p
。
2、代码示例
链表类: LinkedList
package cn.linkedlist.demo05;
import java.util.Iterator;
public class LinkedList<E> implements List<E>
// 创建Node节点
private class Node
// 数据域
E data;
// 指向直接前驱的指针
Node prev;
// 指向直接后继的指针
Node next;
// 构造函数
public Node()
this(null, null, null);
public Node(E data)
this(data, null, null);
public Node(E data, Node prev, Node next)
this.data = data;
this.prev = prev;
this.next = next;
@Override
public String toString()
StringBuilder sb = new StringBuilder();
if (prev != null)
sb.append(prev.data);
else
sb.append("null");
sb.append("->").append(data).append("->");
if (next != null)
sb.append(next.data);
else
sb.append("null");
return sb.toString();
// 链表元素的数量
private int size;
// 声明头结点
private Node head;
// 声明尾节点
private Node tail;
// 初始化头结点
public LinkedList()
head = null;
tail = null;
size = 0;
public LinkedList(E[] arr)
for (E e : arr)
add(e);
//默认向表尾添加元素
@Override
public void add(E element)
add(size, element);
//在链表当中指定索引index处添加一个元素
@Override
public void add(int index, E element)
if (index < 0|| index > size)
throw new ArrayIndexOutOfBoundsException("add index out of bounds");
// 创建新的结点对象
Node node = new Node(element);
// 链表为空
if(isEmpty())
head = node;
tail = node;
tail.next = head;
head.prev = tail;
else if(index == 0) // 在链表头部添加元素
// 头结点的上一跳指向新节点的上一跳
node.prev = head.prev;
node.next = head;
head.prev = node;
head = node;
tail.next = head;
else if(index == size) // 在链表尾部添加元素
node.next = tail.next;
tail.next = node;
node.prev = tail;
tail = node;
head.prev = tail;
else
// 在链表中添加元素
Node p,q; // 定义两个指针变量
if(index <= size / 2)
p = head;
for(int i =0; i < index -1 ; i++)
p = p.next;
q = p.next;
p.next = node;
node.prev = p;
q.prev = node;
node.next = q;
else
p = tail;
for(int i=size -1; i > index; i--)
p = p.prev;
q = p.prev;
q.next = node;
node.prev = q;
p.prev = node;
node.next = p;
size++;
@Override
public int size()
return size;
//查找元素在链表中第一次出现的索引
@Override
public int indexOf(E element)
if(isEmpty())
return -1;
Node p = head;
int index = 0;
while (!p.data.equals(element))
p = p.next;
index++;
if(p == head)
return -1;
return index;
//在链表中判断是否包含元素element
@Override
public boolean contains(E element)
return indexOf(element) != -1;
@Override
public boolean isEmpty()
return size== 0 && head == null && tail == null;
@Override
public void clear()
head = null;
tail = null;
size = 0;
@Override
public String toString()
StringBuilder res = new StringBuilder();
res.append("size=").append(size).append(", [");
Node node = head;
for (int i = 0; i < size; i++)
if (i != 0)
res.append(", ");
res.append(node);
node = node.next;
res.append("]");
return res.toString();
@Override
public Iterator<E> iterator()
return new DoubleCircleLinkedListIterator();
class DoubleCircleLinkedListIterator implements Iterator<E>
private Node cur = head;
private boolean flag = true;
@Override
public boolean hasNext()
if(isEmpty())
return false;
return flag;
@Override
public E next()
E ret = cur.data;
cur = cur.next;
if(cur == head)
flag = false;
return ret;
测试类:LinkedListDemo
package cn.linkedlist.demo05;
public class LinkedListDemo
public static void main(String[] args)
LinkedList<Integer> list = new LinkedList<>();
System.out.println("===链表头部插入===");
// System.out.println(list);
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
System.out.println(list);
System.out.println("===链表尾部插入===");
list.add(list.size(), 4);
list.add(list.size(), 5);
list.add(list.size(), 6);
System.out.println(list);
3、执行结果
1.3 删除操作
1、思路分析
删除头结点
node
节点为head.next
,最终node
是新的头结点。
head
的下一跳置空。
head
的上一跳,给node
的上一跳。
head
的上一跳置空!!head
重新指向node
。
最后让尾指针下一跳重新指向head
即可。
删除尾节点
node
为tail.pre
前驱,最终node
是新的尾结点。
让tail
的上一跳置空。
tail
的下一跳给node
的下一跳,tail
的下一跳置空。
tail
重新指向node
。
head
的上一跳重新指向tail
。
删除中间节点
1、离头部比较近
定义三个指针,p
是要删除节点的前驱,q
是要删除节点,r
是要删除节点的后继,p指针移动到要删除节点的前驱。
让p
的下一跳直接指向r
,让r
的上一跳重新指向p
。
让q
的上一跳和q
的下一跳直接置空。
删除成功。
2、离尾部比较近
定义三个节点指针,p
是要删除节点的前驱,q
是要删除节点,R
是要删除节点的后继。
让R
的上一跳指向p
,让p
的下一跳指向R
,让q
的两边同时置空!!!
最后删除成功!!!
2、代码示例
链表类: LinkedList
//删除链表中指定的元素element
@Override
public void remove(E element)
int index = index0f(element);
if(index != -1)
remove(index);
//删除链表中指定角标处index的元素
@Override
public E remove(int index)
if (index < 0|| index > size)
throw new ArrayIndexOutOfBoundsException("remove index out of bounds");
// 定义ret变量
E ret = null;
Node node;
// 当链表只剩一个元素
if(size ==1)
ret = head.data;
head = null;
tail = null;
// 删除表头
else if(index == 0)
ret = head.data;
node = head.next;
head.next = null;
node.prev = head.prev;
head.prev = null;
head = node;
tail.next = head;
// 删除表尾
else if(index == size -1)
ret = tail.data;
node = tail.prev;
tail.prev = null;
node.next = tail.next;
tail.next = null;
tail = node;
head.prev = tail;
else
// 删除链表中间的某一个元素
Node p, q, r;
if(index <= size / 2)
p = head;
for(int i=0; i < index-1; i++)
p = p.next;
q = p.next;
ret = q.data;
r = q.next;
p.next = r;
r.prev = p;
q.next = null;
q.prev = null;
else
p = tail;
for(int i = size -1; i > index + 1; i--)
p = p.prev;
q = p.prev;
ret = q.data;
r = q.prev;
r.next = p;
p.prev = r;
q.next = null;
q.prev = null;
size --;
return ret;
测试类:LinkedListDemo
package cn.linkedlist.demo05;
public class LinkedListDemo
public static void main(String[] args)
LinkedList<Integer> list = new LinkedList<>();
System.out.println("===链表头部插入===");
//System.out.println(list);
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
System.out.println(list);
System.out.println("===链表尾部插入===");
list.add(list.size(), 4);
list.add(list.size(), 5);
list.add(list.size(), 6);
System.out.println(list);
System.out.println("==删除元素==");
System.out.println(list.remove(3));
System.out.println(list);
3、执行结果
1.4 修改和获取操作
1、代码示例
链表类: LinkedList
//获取链表中指定索引处的元素
@Override
public E get(int index)
if (index < 0|| index > size)
throw new ArrayIndexOutOfBoundsException(查看详情
《链表》之带头双向循环链表(代码片段)
文章目录一、带头双向循环链表概念及结构1、1 带头双向循环链表的概念1、2 带头双向循环链表的结构二、带头双向循环链表的思路及代码实现详解2、1 带头双向循环链表实现思路2、2 带头双向循环链表的模块细节及代码实... 查看详情
双向带头循环链表的(增删查改)的实现(代码片段)
(文章目录)一、双向带头循环链表构成二、双向带头循环链表的实现1.函数的定义和结构体的创建——list.h#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintdatatype;structlistNode datatypeval; structlistNode*prev; structli 查看详情
详解双向循环链表的实现及概念(代码片段)
解剖双向循环链表!!!双向循环链表概念双向链表也叫双链表,是链表的一种,它的每个数据结点都有两个指针,分别指向后继和直接前区。所以,从双向链表中的任意一个结点开始,都可以很... 查看详情
数据结构开发(11):双向循环链表的实现(代码片段)
0.目录1.双向循环链表的实现2.小结1.双向循环链表的实现本节目标:使用Linux内核链表实现StLib中的双向循环链表template<typenameT>classDualCircleList;StLib中双向循环链表的设计思路:数据结点之间在逻辑上构成双向循环链表,头结... 查看详情
c语言带头双向循环链表增删改查的实现(代码片段)
带头双向循环链表:虽然结构比较复杂,一般用在单独存储数据,但实际中使用的链表数据结构大多数都是带头双向循环链表。带头双向循环链表虽然结构复杂,但是实际上实现起来比单链表和顺序表都要更加简... 查看详情
数据结构——带头双向循环链表(代码片段)
目录带头双向循环链表的结构带头双向循环链表的实现建立新节点初始化函数打印函数判空函数尾插函数头插函数尾删函数头删函数查找函数插入函数删除函数销毁函数带头双向循环链表的特点链表和顺序表的对比带头双向循环... 查看详情
带头双向循环链表的实现@线性表(代码片段)
目录0.引1.双向循环链表实现1.1创建、销毁、申请新节点、打印1.1.1创建1.1.2销毁1.1.3申请新节点1.1.4打印1.2尾插、尾删1.2.1尾插1.2.2尾删1.3头插、头删1.3.1头插1.3.2头删1.4查找、任意位置插入、任意位置删除1.4.1查找1.4.2任意位置插入... 查看详情
双向不循环链表(代码片段)
下边程序实现的是一个双向不循环链表。#include<stdio.h>#include<stdlib.h>#include<string.h>#definenew(p)((p)=malloc(sizeof(*(p))))#defineIFNAMSIZ16structinterface*int_last,*int_list;structinterfacestru 查看详情
数据结构开发:循环链表与双向链表(代码片段)
0.目录1.循环链表的实现2.双向链表的实现3.小结1.循环链表的实现什么是循环链表?概念上任意数据元素都有一个前驱和一个后继所有的数据元素的关系构成一个逻辑上的环实现上循环链表是一种特殊的单链表尾结点的指针域保存... 查看详情
c语言教程“双向循环链表”学习总结及其代码实现(代码片段)
双向循环链表和它名字的表意一样,就是把双向链表的两头连接,使其成为了一个环状链表。只需要将表中最后一个节点的next指针指向头节点,头节点的prior指针指向尾节点,链表就能成环儿,如图所示:... 查看详情
java-----循环链表(代码片段)
循环链表1.单向循环链表1.1代码实现2.双向循环链表1.单向循环链表1.1代码实现List:publicinterfaceList<E>voidaddHead(Evalue);voidaddTail(Evalue);voidremoveHead();voidremoveTail();voidremoveValue(Evalue);booleancontains(Eva 查看详情
java-----循环链表(代码片段)
循环链表1.单向循环链表1.1代码实现2.双向循环链表1.单向循环链表1.1代码实现List:publicinterfaceList<E>voidaddHead(Evalue);voidaddTail(Evalue);voidremoveHead();voidremoveTail();voidremoveValue(Evalue);booleancontains(Eval 查看详情
数据结构c语言篇《二》带头双向循环链表实现以及链表相关面试题(下)(代码片段)
循环链表实现及相关面试题(下)链表双向循环链表的实现链表面试题(下)1.合并两个有序链表2.链表分割3.环形链表4.环形链表25.复制带随机指针的链表6.对链表进行插入排序7.删除链表中重复的结点8.链表的回... 查看详情
数据结构学习笔记(单链表单循环链表带头双向循环链表)的增删查改排序等)(代码片段)
数据结构学习笔记(单链表、单循环链表、带头双向循环链表)的增删查改排序等链表的概念及结构链表结构的分类链表的常用操作实现无头单链表单链表补充单循环链表带头双向循环链表链表的概念及结构概念:链... 查看详情
数据结构学习笔记(单链表单循环链表带头双向循环链表)的增删查改排序等)(代码片段)
数据结构学习笔记(单链表、单循环链表、带头双向循环链表)的增删查改排序等链表的概念及结构链表结构的分类链表的常用操作实现无头单链表单链表补充单循环链表带头双向循环链表链表的概念及结构概念:链... 查看详情
第三十三课双向循环链表的实现(代码片段)
头结点不位于链表里面,只是用于定位,和内核链表不同。 将LinuxList.h添加到我们的工程中。再添加一个DualCircleList.h文件:1#ifndefDUALCIRCLELIST_H2#defineDUALCIRCLELIST_H34#include"LinuxList.h"5#include"DualLinkList.h"67 查看详情
数据结构--双向循环链表(代码片段)
...个结点都可以指向它的前驱和后继的链表。java代码实现双向链表类packagesy180923;publicclassDoubleLink<T>//表头privateDNode<T>mHead;//节点个数privateintmCount;publicDoubleLink()//链表表头为空不存数据mHead=newDNode< 查看详情