精华内容
下载资源
问答
  • 解剖双向循环链表!!!

    解剖双向循环链表!!!

    在这里插入图片描述

    双向循环链表概念

    双向链表也叫双链表,是链表的一种,它的每个数据结点都有两个指针,分别指向后继和直接前区。所以,从双向链表中的任意一个结点开始,都可以很方便的访问到它的前驱结点和后继结点。如下图:
    在这里插入图片描述
    可以看出双向循环链表的继承体系,依然实现了List接口!
    在这里插入图片描述

    实现流程图

    当此时只有一个结点元素
    在这里插入图片描述
    此时创建样式如下:
    在这里插入图片描述

    一.元素的添加,链表长度大于等于1时
    1.在双向循环链表的表头添加元素
    在这里插入图片描述
    先断掉头结点的前继然后在指向新节点的前继
    在这里插入图片描述
    最后将head的前继指向新节点,新节点的后继指向head,再把head重新指向新节点,最后把tail结点的后继指向head结点
    在这里插入图片描述
    2.表尾添加一个新元素
    在这里插入图片描述
    表尾添加一个元素是先断掉表尾元素的后继重新指向新节点的后继
    在这里插入图片描述
    接着将tail的后继重新指向给新节点,新节点的前继指向tail结点,最后tail指向新节点,head的前继指向tail结点
    在这里插入图片描述
    3.中间添加元素
    当前一个新节点,add添加到中间插入时
    在这里插入图片描述
    首先我们要找到当前插入结点位置的前一个结点,找到之后也就是图中的结点P,在找到后继结点q,此时把p的后继结点指向新节点,新节点的前继指向p,q的前继指向新节点,新节点的后继指向q。此时便,添加完成!
    在这里插入图片描述
    二.元素的删除
    1.删除此时的头结点
    在这里插入图片描述
    删除头结点首先是将头结点的前继指向后一个node结点的前继续,此时将head的前继设为null,把头结点的后继置为null,再把head重新指向node结点,最后把尾节点的后继指向新head结点
    在这里插入图片描述
    最后删除头结点完成
    在这里插入图片描述
    2.删除尾节点
    在这里插入图片描述
    删除尾接点时,首先将尾节点的后继指向上一个结点的后继,并将尾结点的前继置为null,后继为null,最后把tail指向node结点,再把头结点的前继指向tail结点
    在这里插入图片描述
    在这里插入图片描述
    3.删除中间元素
    在这里插入图片描述
    首先找到删除结点的前继和后继结点
    在这里插入图片描述
    将p的后继指向r结点,r的前继指向p结点
    在这里插入图片描述
    最后将q的前继和后继都置为null,中间删除元素便完成了!
    在这里插入图片描述

    实现代码

    第一部分List接口

    package com.my.接口;
    
    import java.util.Comparator;
    
    public interface
    /*
     * List是线性结构的接口
     * 里面定义了该线性结构的一些通用操作 并支持泛型
     * 继承自Iterable接口(可迭代接口) 主要用于遍历数据结构
     * 其次还有让我们的类可以被foreach循环使用
     * 不是所有的数据结构都可以像数组一样通过角标来访问元素
     */
    List<E> extends Iterable<E> {
    	 /**
         * 在线性结构的末尾添加一个元素element
         * */
        public void add(E element);
        /**
         * 在线性结构指定角标index处添加一个元素element
         * */
        public void add(int index,E element);
        /**
         * 在线性结构中删除指定元素element
         * */
        public void remove(E element);
        /**
         * 在线性结构中删除指定角标index处的元素,并返回
         * */
        public E remove(int index);
        /**
         * 在线性结构中获取指定角标处index的元素
         * */
        public E get(int index);
        /**
         * 在线性结构中修改指定角标处index的元素为新元素element
         * */
        public E set(int index,E element);
        /**
         * 获取线性结构中有效元素的个数
         * */
        public int size();
        /**
         * 获取指定元素element在线性结构中的角标
         * */
        public int indexOf(E element);
        /**
         * 查看线性表中是否包含指定元素element
         * */
        public boolean contains(E element);
        /**
         * 查看线性结构是否为空
         * */
        public boolean isEmpty();
        /**
         * 清空线性结构
         * */
        public void clear();
        /**
         * 对线性结构按照比较器comparator的定义来进行排序
         * */
        public void sort(Comparator<E> comparator);
        /**
         * 获取线性结构中从指定fromIndex角标开始到toIndex角标结尾的所有元素
         * (0 <= fromIndex < toIndex < size)
         * [fromIndex,toIndex)
         * */
        public List<E> sublist(int fromIndex,int toIndex);
    
    }
    
    

    第二部分LinkedList双向循环链表

    package com.my.线性结构;
    
    import java.util.Comparator;
    import java.util.Iterator;
    
    import com.my.接口.List;
    
    public class LinkedList<E> implements List<E> {
    
    	private class Node{
    		Node pre;
    		Node next;
    		E data;
    		public Node(E data) {
    			this.data =data;
    			next = null;
    			pre = null;
    		}
    		@Override
    		public String toString() {
    			// TODO 自动生成的方法存根
    			return data.toString();
    		}
    	}
    	private Node head;
    	private Node tail;
    	private int size;
    	public LinkedList() {
    		head =null;
    		tail = null;
    		size =0;
    	}
    	@Override
    	public Iterator<E> iterator() {
    		// TODO 自动生成的方法存根
    		return null;
    	}
    
    	@Override
    	public void add(E element) {
    		// TODO 自动生成的方法存根
    		add(size,element);
    	}
    
    	@Override
    	public void add(int index, E element) {
    		// TODO 自动生成的方法存根
    		if(index<0||index>size) {
    			throw new IndexOutOfBoundsException("Index is bound!");
    		}
    		Node node  = new Node(element);
    		if(size==0) {//此时表中无元素
    			node.pre = node;
    			node .next=node;
    			head = node;
    			tail = node;
    		}else if(index==0) {//表头添加元素
    			node.pre = head.pre;
    			node.next = head;
    			head.pre = node;
    			head = node;
    			tail.next = head;
    		}else if(index == size) {//表尾添加
    			node.next = tail.next;
    			tail.next = node;
    			node.pre=tail;
    			tail =node;
    			head.pre =tail;
    		}else {//其他情况 也就是在中间添加元素
    			Node p =head;
    			for(int i=0;i<index-1;i++) {
    				p = p.next;
    			}
    			Node q = p.next;
    			p.next=node;
    			node.pre=p;
    			q.pre=node;
    			node.next=p;
    		}
    		size++;
    	}
    
    	@Override
    	public void remove(E element) {
    		// TODO 自动生成的方法存根
    		remove(size);
    	}
    
    	@Override
    	public E remove(int index) {
    		// TODO 自动生成的方法存根
    		if(index<0||index>=size) {
    			throw new IndexOutOfBoundsException("Index is bound!");
    		}
    		E ret =null;
    		if(size==1) {//只有一个元素
    			ret = head.data;
    			head =null;
    			tail =null;
    			size =0;
    		}
    		else if(index==0) {
    			ret = head.data;
    			Node node = head.next;
    			node.pre = head.pre;
    			head.next=null;
    			head.pre =null;
    			head =node;
    			tail.next = head;
    		}else if(index==size-1) {
    			Node node = tail.pre;
    			ret = tail.data;
    			node.next = tail.next;
    			tail.pre = null;
    			tail.next = null;
    			tail =node;
    			head.pre = tail;
    		}else {
    			Node p,q,r,node =head;
    			for(int i=0;i<index-1;i++) {
    				head = head.next;
    			}
    			p = node;
    			q=p.next;
    			ret = q.data;
    			r=q.next;
    			p.next=r;
    			r.pre=p;
    			q.next=null;
    			q.pre=null;
    		}
    		size--;
    		return ret;
    	}
    	@Override
    	public String toString() {
    	// TODO 自动生成的方法存根
    	StringBuilder sb =new StringBuilder();
    	sb.append('{');
    	Node node =head;
    	while(node.next!=head) {
    		sb.append(node.data);
    		node =node.next;
    		sb.append(',');
    	}
    	sb.append(node.data);
    	sb.append('}');
    	return sb.toString();
    	}
    	@Override
    	public E get(int index) {
    		// TODO 自动生成的方法存根
    		if(index<0||index>=size) {
    			throw new IndexOutOfBoundsException("Index is bound!");
    		}
    		E ret = null ;
    		if(index<size/2) {
    			Node p = head;
    			for(int i=0;i<index;i++) {
    				p =p.next;
    			}
    			ret = p.data;
    		}else {
    			Node q = tail;
    			for(int i=size-1;i>index;i--) {
    				q = q.pre;
    			}
    			ret = q.data;
    		}
    		return ret;
    	}
    
    	@Override
    	public E set(int index, E element) {//根据指定下标修改元素
    		// TODO 自动生成的方法存根
    		if(index<0||index>=size) {
    			throw new IndexOutOfBoundsException("Index is bound!");
    		}
    		E ret = null ;
    		if(index<size/2) {
    			Node p = head;
    			for(int i=0;i<index;i++) {
    				p =p.next;
    			}
    			ret = p.data;
    			p.data = element;
    		}else {
    			Node q = tail;
    			for(int i=size-1;i>index;i--) {
    				q = q.pre;
    			}
    			ret = q.data;
    			q.data = element;
    		}
    		return ret;
    	}
    
    	@Override
    	public int size() {//获取有效长度
    		// TODO 自动生成的方法存根
    		return size;
    	}
    
    	@Override
    	public int indexOf(E element) {//查找元素的下标
    		// TODO 自动生成的方法存根
    		if(isEmpty()) {
    			try {
    				throw new IllegalAccessException("NULL!");
    			} catch (IllegalAccessException e) {
    				// TODO 自动生成的 catch 块
    				e.printStackTrace();
    			}
    		}
    		Node node =head;
    		for(int i=0;i<size;i++) {
    			if(node.data.equals(element)) {
    				return i;
    			}
    			node = node.next;
    		}
    		return -1;
    	}
    
    	@Override
    	public boolean contains(E element) {
    		// TODO 自动生成的方法存根
    		return indexOf(element)!=-1;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO 自动生成的方法存根
    		return size==0;
    	}
    
    	@Override
    	public void clear() {
    		// TODO 自动生成的方法存根
    		head =null;
    		tail =null;
    		size =0;
    		
    	}
    
    	@Override
    	public void sort(Comparator<E> comparator) {
    		// TODO 自动生成的方法存根
    		if(comparator==null) {
    			throw new IndexOutOfBoundsException("Is NULL!");
    		}
    		if(size<2) {
    			return;
    		}
    		Node i = head.next;
            Node j = null;
            Node k = null;
            E e = null;
            while(i!=head) {
            	e = i.data;
            	j =i;
            	k = j.pre;
            	while(k!=tail&&comparator.compare(k.data, e)>0) {
            		j.data = k.data;
                    j = j.pre;
                    k = j.pre;
            	}
            	j.data = e;
                i = i.next;
            }
    		
    	}
    
    	@Override
    	public List<E> sublist(int fromIndex, int toIndex) {
    		// TODO 自动生成的方法存根
    		if (fromIndex < 0 || toIndex >= size || fromIndex >= toIndex) {
                throw new IllegalArgumentException("sublist index outof range");
            }
    		Node nodeA = head;
    		for(int i=0;i<fromIndex;i++) {
    			nodeA = nodeA.next;
    		}
    		Node nodeB = head;
    		for(int i=0;i<toIndex;i++) {
    			nodeB = nodeB.next;
    		}
    		LinkedList<E> newList = new LinkedList<>();
    		while(nodeA!=nodeB) {
    			newList.add(nodeA.data);
    			nodeA = nodeA.next;
    		}
    		return newList;
    	}
    
    }
    
    

    测试代码

    package com.my.线性结构;
    
    public class TestS {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		LinkedList list =new LinkedList<>();
    		list.add(new Integer(1));
    		list.add(new Integer(2));
    		list.add(new Integer(3));
    		list.add(new Integer(4));
    		list.add(new Integer(5));
    		list.add(new Integer(6));
    		list.set(5, 10);
    		LinkedList list1 =new LinkedList<>();
    		list1 = (LinkedList) list.sublist(0, 3);
    		System.out.println(list.remove(0));
    		System.out.println(list.get(4));
    		System.out.println(list.indexOf(new Integer(3)));
    		System.out.println(list);
    	}
    
    }
    
    

    结果:
    在这里插入图片描述

    展开全文
  • 双向循环链表 物理存储结构 双向循环链表与单链表一样,都是逻辑连续、物理不连续的存储方式,但它的效果要远远优于单链表,其结构如下: 双向循环链表首先要有一个头节点,头节点中不存放数据,真正的数据从头节点...

    双向循环链表

    物理存储结构

    双向循环链表与单链表一样,都是逻辑连续、物理不连续的存储方式,但它的效果要远远优于单链表,其结构如下:
    双向循环链表
    双向循环链表首先要有一个头节点,头节点中不存放数据,真正的数据从头节点的下一个节点开始存放;然后每一个节点都有两个指针,分别指向前一个节点和后一个节点;最后头尾相连,就成了双向循环链表。

    代码实现

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef int Type;
    typedef struct Node
    {
    	Type data;
    	struct Node* next;   //指向下一个节点
    	struct Node* prev;   //指向前一个节点
    }Node;
    typedef struct Link
    {
    	Node* head;     //头节点
    }Link;
    
    //初始化
    void LinkInit(Link* L);
    //创建节点
    Node* CreateNode(Type data);
    //头插
    void HeadPush(Link* L, Type data);
    //尾插
    void TailPush(Link* L, Type data);
    //在pos位置前插入
    void LinkInsert(Node* pos, Type data);
    //头删
    void HeadPop(Link* L);
    //尾删
    void TailPop(Link* L);
    //删除pos位置元素
    void LinkDelete(Node* pos);
    //查找
    Node* LinkFind(Link* L, Type data);
    //打印
    void LinkPrint(Link* L);
    //销毁
    void LinkDestroy(Link* L);
    //初始化
    void LinkInit(Link* L)
    {
    	L->head = (Node*)malloc(sizeof(Node));
    
    	L->head->data = 0;
    	L->head->next = L->head;
    	L->head->prev = L->head;
    }
    
    //创建节点
    Node* CreateNode(Type data)
    {
    	Node* node = (Node*)malloc(sizeof(Node));
    
    	node->data = data;
    	node->next = NULL;
    	node->prev = NULL;
    
    	return node;
    }
    
    //头插
    void HeadPush(Link* L, Type data)
    {
    	/*Node* node = CreateNode(data);
    	Node* next = L->head->next;
    
    	node->next = next;
    	L->head->next = node;
    
    	next->prev = node;
    	node->prev = L->head;*/
    
    	LinkInsert(L->head->next, data);
    }
    
    //尾插
    void TailPush(Link* L, Type data)
    {
    	/*Node* node = CreateNode(data);
    	Node* last = L->head->prev;
    
    	last->next = node;
    	node->next = L->head;
    
    	node->prev = last;
    	L->head->prev = node;*/
    
    	LinkInsert(L->head, data);
    }
    
    //在pos位置前插入
    void LinkInsert(Node* pos, Type data)
    {
    	Node* node = CreateNode(data);
    	Node* prev = pos->prev;
    
    	prev->next = node;
    	node->next = pos;
    
    	pos->prev = node;
    	node->prev = prev;
    }
    
    //头删
    void HeadPop(Link* L)
    {
    	if (L->head->next == L->head)
    	{
    		return;
    	}
    
    	/*Node* cur = L->head->next;
    	Node* next = cur->next;
    
    	L->head->next = next;
    	next->prev = L->head;
    
    	free(cur);*/
    
    	LinkDelete(L->head->next);
    }
    
    //尾删
    void TailPop(Link* L)
    {
    	if (L->head->next == L->head)
    	{
    		return;
    	}
    
    	/*Node* last = L->head->prev;
    	Node* prev = last->prev;
    
    	L->head->prev = prev;
    	prev->next = L->head;
    
    	free(last);*/
    
    	LinkDelete(L->head->prev);
    }
    
    //删除pos位置元素
    void LinkDelete(Node* pos)
    {
    	if (pos->next == pos)
    	{
    		return;
    	}
    
    	Node* next = pos->next;
    	Node* prev = pos->prev;
    
    	prev->next = next;
    	next->prev = prev;
    
    	free(pos);
    }
    
    //查找
    Node* LinkFind(Link* L, Type data)
    {
    	Node* cur = L->head->next;
    
    	while (cur != L->head)
    	{
    		if (cur->data == data)
    		{
    			return cur;
    		}
    
    		cur = cur->next;
    	}
    
    	return NULL;
    }
    
    //打印
    void LinkPrint(Link* L)
    {
    	Node* cur = L->head->next;
    
    	while (cur != L->head)
    	{
    		printf("%d ", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    //销毁
    void LinkDestroy(Link* L)
    {
    	Node* cur = L->head->next;
    
    	while (cur != L->head)
    	{
    		Node* next = cur->next;
    
    		free(cur);
    		cur = next;
    	}
    
    	free(L->head);
    	L->head = NULL;
    }
    

    优缺点

    优点

    比起单链表和顺序表来说,执行插入删除操作更加方便,时间复杂度均为O(1)

    缺点

    不能像顺序表那样支持随机访问,结构较为复杂
    没有增容的问题,直接用一个开一个

    适用场景

    需要频繁插入删除元素

    展开全文
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示


    前言:
    线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结链表中的双向循环链表,为单链表的结点增加一个指向前驱的指针域,单链表就变成了双链表,将双链表的头尾相连,双链表就成了双向循环链表。

    一、相关概念

    第一部分主要介绍下和链表有关的相关概念,这里给出的概念都是书本上的官方定义,并不是作者胡诌的,为什么给出这些官方的定义呢 ?因为笔者认为官方给出的定义,是对一个概念最本质的解释,它的解释经过了时间的考验,被认为是解释的最合理深入简明扼要的。

    1.什么是线性表

    线性表是由n个数据元素构成的有限序列,n为线性表的表长,当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱,终端节点没有后继,其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。

    2.什么是顺序表

    采用顺序存储结构存储数据元素的线性表被称为顺序表,顺序表,要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的,当在顺序表的第i(0<=i<=n)插入一个数据元素时,需要后移n-i+1个数据元素,当删除第i个元素时需要移动n-i个数据元素。java实现顺序表

    3.什么是链表

    采用链式存储结构存储数据元素的线性表被称为链表,链表不要求逻辑上相邻的数据元素内存上必须相邻,链表的每个节点都包含两部分,一部分是数据域用以存储数据,一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时,被称为单链表。单链表-含头结点单链表-不含头结点

    4.单链表、双链表、循环单链表、循环双链表

    当链表的结点只有一个指针域时被称为单链表,循环单链表是单链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    当链表的结点有两个时,一个指向前驱,一个指向后继这种链表便是双链表,循环双链表是双链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    所有的链表的实现均有两种方式,一种是带有头结点,一种是不带有头结点的实现方式,两种实现略有区别。

    5.为什么需要循环链表?

    循环链表一般就是指循环单链表,不特殊指明是双向循环链表,那么该名称描述的就是单项循环链表,之所以需要循环链表是因为在操作系统中,循环链表有特定的应用场景,在一些场景中,链表中的元素需要循环的执行,但是在实际的开发中应用最多的还是双向循环链表。

    6.为什么需要双向链表?

    若是给定了一个结点,根据当前结点获取该结点的上一个结点,那么我们是没有办法直接获取的,只能是遍历链表,但若是使用了双向链表,我们则可以直接获取到该元素的上一个结点,时间复杂度就变成了O(1)。所以双向链表的实际应用意义更强,将双向链表的首尾相连就成了双向循环链表,双向循环链表的应用最常见的就是LinkedList。

    7.头结点和首结点

    首节点:真正存储第一个数据元素的结点被称为首节点。
    头结点:当链表采用带头结点方式实现时,会创建一个数据域为null的节点,该节点的指针域存储的指针指向首节点的指针,他的唯一作用是标识链表的开始,带有头结点的链表更易于操作。

    8.常见的栈和队列与线性表的关系

    栈和队列也是常见的数据结构,但是栈和队列并不是线性表的一种,线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢,栈是被限制了只能在一端进行插入和删除操作的线性表,所以栈的特性是先入后出,队列是被限制了只能在一端插入另一端删除的线性表,所以队列的特性是先入先出。既然栈和队列都是特殊的线性表,那么栈和队列自然就可以使用线性表来实现了,通常可以使用线性表中的顺序表和队列来实现栈和队列。

    二、实现过程

    单链表-含头结点
    单链表-不含头结点
    上面是两种单链表的实现方式,其实无论是双链表还是双向循环链表他的实现方式都是类似的,区别都很有限,上面两篇文章里详细实现了单链表的各种常用方法,因此在该文章里只会总结必须用到的几个方法,比如插入、删除、清空、长度、判空、根据下标获取等,其他方法的实现都不难,就不一一展示了。

    1.提供节点类:DupNode

    双向循环链表的实现,我们首先必须为其提供一个结点类,该类需要有三个属性,一个数据域,一个指向前驱的指针域,还有一个指向后继的指针域,然后提供必要的构造方法即可,如下:

    /**
     * @author pcc
     * @version 1.0.0
     * @className DupNode
     * @date 2021-04-19 16:43
     * 该类是双向链表的结点类
     * 该类包含了数据域,后继指针域、前驱指针域三个属性。
     */
    public class DupNode {
        Object object;
        DupNode prior;//前驱指针域
        DupNode next;//后继指针域
    
        public DupNode(){
            this(null);
        }
        public DupNode(Object object){
            this(object,null,null);
        }
        public DupNode(Object object,DupNode prior,DupNode next){
            this.object = object;
            this.prior = prior;
            this.next = next;
        }
    }
    

    2.提供双向循环链表的实现类:DoubleLinkedTable

    采用带有头结点的方式实现双向循环链表,因此我们需要定义一个头结点。然后提供初始化它的构造器。值得注意的是,在初始化头结点时,我们必须将他的前驱和后继都声明为自己,这样才是一个空的双向循环链表。

    public class DoubleLinkedTable {
        //头结点
        DupNode head;
    
        public DoubleLinkedTable(){
            head = new DupNode();
            head.prior = head;
            head.next = head;
        }
    }
    

    3.提供长度(length)、打印(display)、清空(clear)等方法

    这些方法的实现原理都很简单,求链表长就是遍历链表计数即可,打印也是遍历链表,清空则是将头结点的前驱和后继都声明为自己,下面是三个方法的实现:

        //长度
        public int length(){
            DupNode node = head.next;
            int j = 0;
            while(!node.equals(head)){
                j++;
                node = node.next;
            }
            return j;
        }
    
        //打印
        public void display(){
            DupNode node = head.next;
            while(!node.equals(head)){
                System.out.println(node.object);
                node = node.next;
            }
        }
        //清空
        public void clear(){
            head.next = head;
            head.prior = head;
        }
    

    4.提供根据下标插入方法:insert(int i,Object object)
    学习双向循环链表建议还是先学习单链表,会了单链表双向循环链表就是窗户纸,一桶就破,因为他们的实现思路都是一样的,只是稍微的变化而已。单链表的遍历我们的退出条件是找到尾结点就退出(node.next == null),循环链表肯定没有尾结点了,退出循环的条件就成了碰到头结点再退出(node ==head),另外一点区别就是双向循环链表的赋值问题,我们需要为新结点的前驱指针和后继指针赋值,同时需要为新结点的上一个节点的后继后继指针从新赋值,还需要为新节点的后继结点的前驱指针重新赋值,代码实现如下:

       /**
         * 思路:
         * 1.寻找下标为i-1的数据元素,注意退出循环的条件应该是node!=head
         * 2.赋值即可,循环链表的核心就是空表也会有循环体系
         * 3,赋值时,i+1位置的元素应该是node.next 所以,应为node.next最后赋值
         * @param i
         * @param object
         * @throws Exception
         */
        public void insert(int i,Object object) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
             DupNode node = head;
             int j = 0;
             while(!node.next.equals(head) && j<i){
                 j++;
                 node = node.next;
             }
    //         DupNode newNode = new DupNode(object);
    //         node.next.prior = newNode;
    //         newNode.prior = node;
    //         newNode.next = node.next;
    //         node.next = newNode;
    
            //写成以下这种和上面注释的部分,效果一样,无区别
             DupNode newNode = new DupNode(object,node,node.next);
             node.next.prior = newNode;
             node.next = newNode;
        }
    

    到了这里,我们就可以初步测试下,双向链表的插入是否有效了,下面创建一个测试类测试下,如下图所示,将几个元素插入到了双向循环链表中,然后输出结果正常,说明插入方法实现无误。有了这些头插法、尾插法直接根据下标即可轻松实现,这里不展示了。
    在这里插入图片描述

    5.提供根据下标删除的方法:remove(int i)

    实现思路其实和单链表的删除是没有区别的:寻找到下标为i-1的数据元素,然后将他的后继更改为i+1的数据元素,然后将下标为i+1的数据元素的前驱更改为,下标为i-1的数据元素即可,实现如下:

        //删除
        public void remove(int i) throws Exception{
            if(i<0 || i>length()-1)
                throw new Exception("下标不合法");
            DupNode node = head;
            int j = 0;
            while(!node.next.equals(head) && j<i){
                j++;
                node = node.next;
            }
            node.next = node.next.next;
            node.next.prior = node;
        }
    

    然后来测试下删除方法,就测试下删除下标为2的元素吧,理论上删除后,输出的应该是:张三、李四、赵柳,如下图可见,输出无误,可见删除方法实现时无误的。
    在这里插入图片描述

    6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)

    上面也说过,双向链表解决的问题就是在获取指定结点的上一个结点时是无需遍历链表的,这样大大节省了时间成本,这里就测试下该方法的实现。三个方法的实现如下所示:

        //根据下标获取
        public Object get(int i) throws Exception{
            return getNode(i).object;
        }
    
        //根据下标获取其前一个元素
        public Object getPrior(int i) throws Exception{
            return getNode(i).prior.object;
        }
    
        //根据下标获取其后一个元素
        public Object getNext(int i) throws Exception{
            return getNode(i).next.object;
        }
    
        public DupNode getNode(int i) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
            DupNode node = head.next;
            int j =0;
            while(node.equals(head) && j<i){
                j++;
                node = node.next;
            }
            return node;
        }
    

    下面我们来测试下这三个方法是否正确,使用李四所在结点来进行测试,李四的下标应该是1,传入1分别运行三个方法,若是正确应该输出的是:李四、张三、王五,如下图可见结果正确。
    在这里插入图片描述

    三、总结

    1.链表的缺点

    线性表的两种实现顺序表、链表。相比于顺序表,链表的缺点就是查找元素比较慢,查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1),在查找上顺序表要优于链表,链表查找慢,就是它的缺点了,但是双向循环链表在一定程度上减少了查找时的时间复杂度,但是依然是不及顺序表的查找效率的,所以具体的使用场景还是静态数据适合使用顺序表,动态数据适合使用链表。

    2.链表的优点

    顺序表在指定下标x位置插入元素,组需要后移n-x+1个元素,若是删除下标为x的数据元素,则需要向前移动n-x个数据元素,但是链表则不需要移动任何元素,链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1),而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。

    3.如何使用链表

    所以综合链表的优点与缺点我们可以发现,顺序表更适合存储“静态”型数据,而链表更适合存储“动态”型数据,何为动态型呢,就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList,链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。

    展开全文
  • 双向循环链表的删除

    2021-10-16 21:35:25
    建立双向循环链表,实现双向循环链表的删除操作。 #include <stdio.h> int nodeNum = 5; struct node { int t; node * llink; node * rlink; }; //建表 struct node *creatlist() { int i = 0; int...

    建立双向循环链表,实现双向循环链表的删除操作。

    #include <stdio.h>
    
    int nodeNum = 5;
    
    struct node
    {
    	int t;
    	node * llink;
    	node * rlink;
    };
    
    //建表 
    struct node *creatlist()
    {
    	int i = 0;
    	int t;
    	struct node *head, *p, *q;
    	//头结点
    	scanf_s("%d", &t);
    	head = new struct node;
    	head->t = t;
    	head->llink = 0;
    	head->rlink = 0;
    	q = head;
    
    	for (i = 0; i < nodeNum - 1; i++) {
    		scanf_s("%d", &t);
    		p = new struct node;
    		p->t = t;
    		p->llink = q;
    		p->rlink = 0;
    		q->rlink = p;
    		q = q->rlink;
    	}
    
    	q->rlink = head;
    	head->llink = q;
    	return head;
    }
    
    //删除
    struct node *deleteOne(struct node *head, int i)
    {
    	if (head == 0) {
    		printf("这是个空表\n");
    		return head;
    	}
    	else if (i<0 || i>nodeNum) {
    		printf("指定元素不存在\n");
    		return head;
    	}
    	//可以删除
    	struct node *q;
    	if (i == 0) {
    		q = head;
    		head = head->rlink;
    	}
    	else if(i < nodeNum / 2){
    		struct node *p;
    		p = head;
    		//从左往右找
    		for (int j = 0; j < i - 1; j++) {
    			p = p->rlink;
    		}
    		q = p->rlink;
    		p->rlink = q->rlink;
    		q->rlink->llink = p;
    	}
    	else {
    		struct node *p;
    		p = head;
    		//从右往左找
    		for (int j = 0; j < nodeNum - i - 1; j++) {
    			p = p->llink;
    		}
    		q = p->llink;
    		p->llink = q->llink;
    		q->llink->rlink = p;
    	}
    	delete q;
    	nodeNum--;
    	return head;
    }
    
    //打印
    void print(struct node *head)
    {
    	struct node *tmp = head;
    	int i = 0;
    
    	while (i < nodeNum)
    	{
    		printf("%d ", tmp->t);
    		tmp = tmp->rlink;
    		i++;
    	}
    	printf("\n");
    }
    
    //释放
    void removeAll(struct node *head)
    {
    	struct node*p = head;
    	for (int i = 0; i < nodeNum; i++) {
    		p = head;
    		head = head->rlink;
    		delete p;
    		nodeNum = 0;
    	}
    }
    
    int main()
    {
    	int i;
    	struct node *head = NULL;
    	struct node *h = NULL;
    	//创建链表
    	printf("输入5个值\n");
    	head = creatlist();
    
    	//删除
    	printf("删除第几个元素\n");
    	scanf_s("%d", &i);
    	i = i - 1;
    	head = deleteOne(head, i);
    	//head = deleteOne(h, i);//空链表
    
    	//打印单链表
    	printf("删除后的链表为:\n");
    	print(head);
    
    	//释放
    	removeAll(head);
    
    	return 0;
    }

     

    展开全文
  • 1.什么是双向循环链表双向循环链表结构是两个指针,一个头指针(指向链表的头部),一个尾指针(指向链表的尾部),当前循环链表的长度size. 每个节点LinedNode由一个前向的指针,一个后向的指针,一个当前节点...
  • 双向循环链表讲解及实现

    千次阅读 多人点赞 2021-04-08 19:39:36
    带头双向循环链表二.实现(1).动态申请一个结点 一.带头双向循环链表 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个链表虽然结构复杂,但是使用...
  • 利用双向循环链表作为储存结构设计并实现一个通讯录程序。可以实现信息的添加、插入、删除、查询和统计等功能 1.2 课程设计要求 (1) 每条信息至少包含:姓名(name)、街道(street)、城市(city)、邮编、(eip...
  • 双向链表的建立和单链表的建立差不多,只不过单链表只是指向一个方向,而双链表指向两个方向。...首先我们先创立一个表头,即只有一个节点的循环链表,只有一个节点意味着front指针和tail指针都指向自身 //创建表头 d
  • 双向链表插入、删除、与创建的原理: 其实双向链表和单链表的区别主要是在节点的结构上,因为节点结构不同,进而导致相关操作较单链表也就有了一些差异;双向链表,顾名思义,从头可以到尾,由尾也可以到头;双向...
  • 双向循环链表:就是在双向链表的基础之上把头节点和尾结点也用两个指针相互链接,形成一个环: 结构我们懂了那么接下来开始我们的准备工作 : #include<stdio.h> #include<stdlib.h> struct node { ...
  • 双向循环链表的实现详解

    千次阅读 2019-05-09 16:47:57
    双向循环链表直接体现为 双向和循环,一般的单链表只有节点数据data和next指向地址(应该也是引用的意思),而在此需要增加前面部分的pre指向地址,同时还需要循环 循环则在定义节点时可以解决,如下所示 即假想只有...
  •   与单链表不同,每一个节点都增加了一个指向前驱的节点,并且首届点和尾节点分别指向开头与结尾,构成双向循环链表。   接下来的篇幅,主要讲述双向链表与单链表操作的不同之处。 二. 基础操作 1. 在指定位置...
  • 不带头结点的双向循环链表

    千次阅读 2019-05-21 18:46:36
    基本概念 循环链表:将单链表中最后一个结点的next指向头结点或者空指针,就使得整个单链表形成一个环,这种头尾相接的单链表...双向循环链表:将二者结合起来,结点有两个指针域,且最后一个结点的next指向...
  • 查找方向可以是从左往右也可以是从右往左,但是要实现从右往左还需要终端节点的地址,所以通常会设计成双向循环链表; 双向循环链表 循环链表指得是终端节点的next指向head节点,head的prior指向终端节点 若链表为...
  • C语言双向循环链表

    2021-08-07 20:03:39
    在C语言中,链表分为单向链表双向链表,单向链表只能朝一个方向遍历,中间的一个节点只能由上一个节点推出,只能往前推,无法往后推,关于单向链表的介绍可以点击单向链表介绍。 这次介绍双向链表,既然叫双向就...
  • 我们常常会用到的链表有:单向链表、双向链表和循环链表。 链表不同于数组的地方在于:它的物理存储结构是非连续的,也就是说链表在内存中不是连续的,并且无序。它是通过数据节点的互相指向实现,当前节点除了存储...
  • 长整数四则运算_双向循环链表

    千次阅读 2017-04-07 11:51:27
    利用双向循环链表实现长整数的存储, 每个结点含一个整型变量. 任何整型变量的范围是 -(215-1)~(215-1)。输入和输出形式: 按中国对于长整数的表 示习惯, 每四位一组,组间用逗号隔开。 [ 测试数据 ] (1) 0;0;应...
  • 双向链表单个节点结构:双向链表节点双向链表的数据结构:双向链表数据结构双向链表的插入操作插入数据到链表尾部链表尾部插入数据插入数据到链表中间链表中部插入数据双向列表删除操作删除链表...
  • 循环链表 特点: 在整个链表当中没有最后一个结点。 当链表中只有一个结点的时候,那么这个结点的下一个结点是他本身。 Java实现代码 package com.xingyun.linked; /* * * 循环链表的实现。不存在最后...
  • 双向链表原理

    2019-08-16 09:35:18
    一般我们都构造双向循环链表。 双向链表的主要优点是对于任意给的结点,都可以很轻易的获取其前结点和后结点,其主要缺点是每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作...
  • 本文详解了内核中面向对象的list结构的原理,以及如何以list为内嵌对象来构造自己的链表结构,如何从内嵌list对象获得自定义的对象指针;探讨了各种宏或者函数的详细使用...【关键字】双向循环链表,list,lis
  • 本文实例讲述了Python单向链表和双向链表原理与用法。分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大。 链表由一个个节点组成。 单向链表的...
  • 双向链表其实是单链表的改进。当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域...
  • 双向链表也叫双链表,它的每个...别人常常来构造双向循环链表,今天我们特立独行一下,先来尝试构造双向非循环链表。示例代码上传至 https://github.com/chenyufeng1991/DoubleLinkedList 。构造节点:typedef struct
  • 谢谢各位师哥师姐,么么哒 这是 节点定义 template struct DoubleNode { T data; DoubleNode<T> *right; DoubleNode<T> *left;... DoubleNode(const T& data, DoubleNode* right,DoubleNode* left) ...
  • 一、双向链表原理顾名思义,双向链表跟单链表和循环列表最大的差别,就是同时拥有前驱指针和后驱指针,基于这一个特性,查询某结点的前一个结点,时间复杂度可以达到O(1),非常高效。双向链表的存取时间复杂度是O(n)...
  • 概念 我们常说的单链表是有向的链表,因为链表1中有next指针它对应指向链表2的地址...双向循环链表则是头尾相连的双向链表 结构定义 typedef struct Double{ ElemType data; struct Double * next,* prior; }Dou...
  • 操作 时间复杂度(T(n)) 空间复杂度(S(n)) 判断是否为空 ...转置链表 O(n) O(1) 得到指定下标的元素 O(n) O(1) 得到指定元素的下标
  • package design; import java.util.Scanner;...//循环链表 public class LinkedList<AnyType> { private int theSize; private Node<AnyType> beginMarker; private Node<AnyType> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,915
精华内容 11,966
关键字:

双向循环链表原理