精华内容
下载资源
问答
  • 本文实例讲述了python双向链表原理与实现方法。分享给大家供大家参考,具体如下: 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向...
  • 本文实例讲述了Python单向链表和双向链表原理与用法。分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大。 链表由一个个节点组成。 单向链表的...
  • 双向链表原理

    2019-08-16 09:35:18
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    双向链表的主要优点是对于任意给的结点,都可以很轻易的获取其前结点和后结点,其主要缺点是每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作也将更加耗时,因为需要操作更多的指向操作。

    1.双向链表单个节点结构:( 双向链表节点)
    在这里插入图片描述
    2.双向链表的数据结构:
    在这里插入图片描述
    3.双向链表的插入操作
    (1)插入数据到链表尾部
    在这里插入图片描述
    (2)插入数据到链表中间
    在这里插入图片描述
    4.双向列表删除操作
    (1)删除链表尾部数据
    在这里插入图片描述
    (2)删除链表中间数据
    在这里插入图片描述
    5.循环双向列表设计
    循环双向链表是在普通双向链表基础上进化得到的。在普通的双向链表中,如果我们要获取最后一个节点的时候,我们只能从头开始遍历,一直遍历到最后才能够拿到最后一个节点的数据。而循环双向链表会把header的prev指向最后一个节点,最后一个节点next指向header。其数据结构如图所示:
    在这里插入图片描述
    循环链表的添加、删除和普通的双向链表是一模一样的,这里就不再赘述。

    展开全文
  • 图文详解双向链表原理

    千次阅读 2019-10-13 18:44:23
    双向链表 双向链表的主要优点: 对于任意给的结点,都可以很轻易的获取其前结点和后结点。 其主要缺点:每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作也将更加耗时,因为...

    双向链表

    双向链表的主要优点: 对于任意给的结点,都可以很轻易的获取其前结点和后结点。
    其主要缺点:每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作也将更加耗时,因为需要操作更多的指向操作。

    双向链表单个节点结构:
    在这里插入图片描述
    双向链表的数据结构:
    在这里插入图片描述

    双向链表的插入操作

    插入数据到链表尾部
    在这里插入图片描述
    插入数据到链表中间
    在这里插入图片描述

    双向列表删除操作

    删除链表尾部数据
    在这里插入图片描述
    删除链表中间数据
    在这里插入图片描述

    循环双向列表设计

    循环双向链表 是在普通双向链表基础上进化得到的。在普通的双向链表中,如果我们要获取最后一个节点的时候,我们只能从头开始遍历,一直遍历到最后才能够拿到最后一个节点的数据。而循环双向链表会把header的prev指向最后一个节点,最后一个节点next指向header。其数据结构如图所示:
    在这里插入图片描述
    循环链表的添加、删除和普通的双向链表是一模一样的,这里就不再赘述。

    展开全文
  • 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。 操作 is_...

    双向链表
    一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
    在这里插入图片描述
    操作
    is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历链表
    add(item) 链表头部添加
    append(item) 链表尾部添加
    insert(pos, item) 指定位置添加
    remove(item) 删除节点
    search(item) 查找节点是否存在
    实现

    class Node(object):
        """双向链表节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
    
    
    class DLinkList(object):
        """双向链表"""
        def __init__(self):
            self.__head = None
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """返回链表的长度"""
            cur = self.__head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            cur = self.__head
            while cur != None:
                print cur.item,
                cur = cur.next
            print ""
    
        def add(self, item):
            """头部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表,将_head指向node
                self.__head = node
            else:
                # 将node的next指向_head的头节点
                node.next = self.__head
                # 将_head的头节点的prev指向node
                self.__head.prev = node
                # 将_head 指向node
                self.__head = node
    
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表,将_head指向node
                self.__head = node
            else:
                # 移动到链表尾部
                cur = self.__head
                while cur.next != None:
                    cur = cur.next
                # 将尾节点cur的next指向node
                cur.next = node
                # 将node的prev指向cur
                node.prev = cur
    
    
    
        def search(self, item):
            """查找元素是否存在"""
            cur = self.__head
            while cur != None:
                if cur.item == item:
                    return True
                cur = cur.next
            return False
    

    指定位置插入节点
    在这里插入图片描述

    def insert(self, pos, item):
            """在指定位置添加节点"""
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
                node = Node(item)
                cur = self.__head
                count = 0
                # 移动到指定位置的前一个位置
                while count < (pos-1):
                    count += 1
                    cur = cur.next
                # 将node的prev指向cur
                node.prev = cur
                # 将node的next指向cur的下一个节点
                node.next = cur.next
                # 将cur的下一个节点的prev指向node
                cur.next.prev = node
                # 将cur的next指向node
                cur.next = node
    

    删除元素
    在这里插入图片描述

    def remove(self, item):
            """删除元素"""
            cur = self.__head
            while cur != None:
                # 找到了要删除的元素
                if cur.item == item:
                    # 先判断此结点是否是头节点
                    # 头节点
                    if cur == self.__head:
                        self.__head = cur.next
                        # 如果存在下一个结点,则设置下一个结点
                        if cur.next:
                            # 判断链表是否只有一个结点
                            cur.next.prev = None
                    else:
                        cur.prev.next = cur.next
                        # 如果存在下一个结点,则设置下一个结点
                        if cur.next:
                            cur.next.prev = cur.prev
                    break
                else:
                    cur = cur.next
    

    测试

    if __name__ == "__main__":
        ll = DLinkList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        ll.insert(4, 5)
        ll.insert(0, 6)
        print "length:",ll.length()
        ll.travel()
        print ll.search(3)
        print ll.search(4)
        ll.remove(1)
        print "length:",ll.length()
        ll.travel()
    
    展开全文
  • 相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
  • 双向链表基本原理双向链表也是链表的一种,它每个数据结点中都有两个结点,分别指向其直接前驱和直接后继。所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。 双向链表的结构如下图...

    双向链表基本原理:

    双向链表也是链表的一种,它每个数据结点中都有两个结点,分别指向其直接前驱和直接后继。所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。
    双向链表的结构如下图所示:
    在这里插入图片描述

    双向链表的基本操作:

    分析 双向链表的遍历,添加,修改,删除的操作思路

    1. 遍历:和单链表一样,只是可以向前,也可以向后查找
    2. 添加 (默认添加到双向链表的最后):
      (1) 先找到双向链表的最后这个节点
      (2) temp.next = newHeroNode
      (3) newHeroNode.pre = temp;
    3. 修改:思路和原来的单向链表一样.
    4. 删除:
      (1) 因为是双向链表,因此,我们可以实现自我删除某个节点
      (2) 直接找到要删除的这个节点,比如temp
      (3) temp.pre.next = temp.next
      (4) temp.next.pre = temp.pre;

    代码实现:

    package LinkedList;
    
    public class DoubleLinkListDemo {
    	public static void main(String[] args) {
    		System.out.println("双向链表的测试");
    		// 先创建节点
    		HeroNod hero1 = new HeroNod(1, "宋江", "及时雨");
    		HeroNod hero2 = new HeroNod(2, "卢俊义", "玉麒麟");
    		HeroNod hero3 = new HeroNod(3, "吴用", "智多星");
    		HeroNod hero4 = new HeroNod(4, "林冲", "豹子头");
    		// 创建一个双向链表
    		DoubleLinkList doubleLinkList = new DoubleLinkList();
    		doubleLinkList.add(hero1);
    		doubleLinkList.add(hero2);
    		doubleLinkList.add(hero3);
    		doubleLinkList.add(hero4);
    		System.out.println("修改前");
    		doubleLinkList.list();
    
    		HeroNod newHeroNode = new HeroNod(4, "公孙胜", "入云龙");
    		doubleLinkList.update(newHeroNode);
    		System.out.println("修改后");
    		doubleLinkList.list();
    
    		HeroNod new2HeroNode = new HeroNod(2, "卢俊义", "玉麒麟");
    		doubleLinkList.delete(new2HeroNode);
    		System.out.println("删除后");
    		doubleLinkList.list();
    
    	}
    
    }
    
    class DoubleLinkList {
    	private HeroNod head = new HeroNod(0, "", "");
    
    	// 向list中添加节点
    	public HeroNod getHead() {
    		return head;
    	}
    
    	// 遍历双向链表
    	public void list() {
    		if (head.next == null) {
    			System.out.println("该链表为空,无法遍历");
    			return;
    		}
    		HeroNod temp = head.next;
    		while (true) {
    			if (temp == null)
    				break;
    			System.out.println(temp);
    			temp = temp.next;
    		}
    	}
    
    	// 向双向链表中
    	public void add(HeroNod heronode) {
    		HeroNod temp = head;
    		while (true) {
    			if (temp.next == null)// 链表的辅助变量temp指向链表的最后一个元素
    				break;
    			temp = temp.next;
    		}
    		temp.next = heronode;
    		heronode.pre = temp;
    	}
    
    	// 修改双向链表中指定的值
    	public void update(HeroNod heronode) {
    		if (head.next == null) {
    			System.out.println("双向链表为空,无法修改指定元素");
    			return;
    		}
    		HeroNod temp = head.next;
    		boolean flag = false;
    		while (true) {
    			// 已遍历到链表的终点
    			if (temp == null) {
    				break;
    			}
    			// 找到要修改的no
    			if (temp.no == heronode.no) {
    				flag = true;
    				break;
    			}
    			// 跳转到下一个节点
    			temp = temp.next;
    		}
    		if (flag == false) {
    			System.out.println("链表中不存在要修改的元素的no");
    			return;
    		} else {
    			temp.name = heronode.name;
    			temp.nickName = heronode.nickName;
    		}
    	}
    
    	// 删除指定节点
    	public void delete(HeroNod heronode) {
    		HeroNod temp = head.next;
    		boolean flag = false;
    		while (true) {
    			if (temp == null)
    				break;
    			if (temp.no == heronode.no) {
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		if (flag == true) {
    			temp.pre.next = temp.next;
    			temp.next.pre = temp.pre;
    		} else {
    			System.out.println("链表中不存在要删除的元素的no");
    			return;
    		}
    	}
    }
    
    class HeroNod {
    	public int no;
    	public String name;
    	public String nickName;
    	public HeroNod next;
    	public HeroNod pre;
    
    	public HeroNod(int no, String name, String nickName) {
    		super();
    		this.no = no;
    		this.name = name;
    		this.nickName = nickName;
    	}
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
    	}
    }
    

    输出:

    双向链表的测试
    修改前
    HeroNode [no=1, name=宋江, nickName=及时雨]
    HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
    HeroNode [no=3, name=吴用, nickName=智多星]
    HeroNode [no=4, name=林冲, nickName=豹子头]
    修改后
    HeroNode [no=1, name=宋江, nickName=及时雨]
    HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
    HeroNode [no=3, name=吴用, nickName=智多星]
    HeroNode [no=4, name=公孙胜, nickName=入云龙]
    删除后
    HeroNode [no=1, name=宋江, nickName=及时雨]
    HeroNode [no=3, name=吴用, nickName=智多星]
    HeroNode [no=4, name=公孙胜, nickName=入云龙]
    

    为何要引入双向链表:

    1、单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
    2、单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到temp,temp是待删除节点的前一个节点。

    展开全文
  • 何为链表 摘要 : 链式结构是一种使用对象引用变量来创建对象间的链的数据结构。对象引用变量可以用于创建链式结构,对象引用变量所存储的特定地址一般无关紧要。换句话说,重要的是能够使用引用变量来访问对象,而...
  • 单链表的节点有item和next,而双向链表的节点还必须有一个指向前一个节点的prior(别的命名也行,反正必须有个东西指向前一个节点)。prior存在的意义也是为了更好地查找节点的前驱节点。因此必须对Node进行改造。 ...
  • 二叉树与双向链表

    2019-01-06 17:55:46
    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; ...
  • 双向链表的实现原理

    2021-02-23 23:51:20
    链表(LinkedList)具有的特性 顺序访问会非常高效,而随机访问效率比较低 插入、删除操作效率比较高 链表实现的关键 linkedList为双链表,里面维护了一个first和last指针,而每个节点有item自身、prev和next两个...
  • STL—list(双向链表)详解

    千次阅读 2019-03-17 16:25:54
     list 容器视线里双向链表的数据结构,数据元素通过链表指针连城逻辑意义上的线性表,这样,对链表的任一位置的元素进行插入、删除和查找都会是极快的。下图是list 采用的双向循环链表的结构示意图。  list 的每...
  • 双向链表 双向链表与链表的区别在于,双向链表有指向前一个节点的指针,可以获取到前一个节点。 获取值的时候,可以判断index下标所在的位置,从而决定从首节点开始查找还是从尾节点开始查找 public class ...
  • 文章目录1 链表介绍 1 链表介绍 链表是以节点的方式来存储的,是链式存储 每个节点包含data域,next域:指向下一个节点 如下图,发现链表的各个节点不一定是连续存储的 链表分带头节点的链表和没有头节点的链表,...
  • 295基于双向链表的双向冒泡排序法 描述 有n个记录存储在带头结点的双向链表中,利用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。 输入 多组...
  • 主要介绍了Python数据结构之双向链表的定义与使用方法,结合实例形式分析了Python双向链表的概念、原理、使用方法及相关注意事项,需要的朋友可以参考下
  • 代码解释 思路,代码已经通过leetcode 检测 public class LRUCache { private int capacity;... // 定义俩个节点,用来串起整个双向链表 head 和tail的作用见图 private CacheNode head = new CacheNode(-1, -1);
  • 本文实例讲述了JS双向链表实现与使用方法。分享给大家供大家参考,具体如下: 前面一篇讲述了《JS基于对象的链表实现与使用方法》,这里的双向链表通过增加一个previous属性实现。 单链表中若需要查找某一个元素时,...
  • 内核双向链表

    2019-10-08 20:09:22
    链表分为单向链表与双向链表,一般的实现就是在结构体中内嵌指向下一个元素的指针。例如:structname{intnum;...;structname*next;structname*prev;}但是linux内核中的实现确有点特殊他是通过独立定义一个链表结构...
  • JavaScript实现双向链表

    2020-08-14 14:22:29
    JavaScript实现双向链表 一、双向链表简介 双向链表:既可以从头遍历到尾,又可以从尾遍历到头。也就是说链表连接的过程是双向的,它的实现原理是:一个节点既有向前连接的引用,也有一个向后连接的引用。 双向...
  • 前言 我是刚入门计算机的一只菜鸡,目前在学习数据结构与算法。近期碰到了双向链表代码实现这块硬骨头,花了半天的时间研究,我...双向链表原理 原创文章 3获赞 1访问量 1909 关注 私信 展开阅读全文 作者:
  • 双向链表的使用

    2020-11-05 15:59:23
    1.单向链表和双向链表优缺点的分析 1.单向链表查找的方向只能是一个方向,而双向链表可以向前或者向后查找 2.单向链表不能自我删除,需要借助辅助节点,而双向链表,则可以实现自我删除,所以,单链表删除节点时,...
  • java模拟双向链表实现

    千次阅读 2019-03-10 20:11:17
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点 下图是双向链表的逻辑结构图...
  • C++实现双向链表

    万次阅读 多人点赞 2018-07-10 15:29:06
    下面就是我们双向链表的基本原理。这里我们插入代码案例:头文件DoubleLink.h#ifndef DOUBLE_LINK_HXX #define DOUBLE_LINK_HXX #include &lt;iostream&gt; using namespace std; //一个节点 template&...
  • 单向链表、双向链表

    2020-07-12 20:51:54
    单向链表 链表和数组一样,都可以用于存储一系列的元素。链表的每个结点(最后一个结点除外)由一个存储元素本身的结点的数据和一个指向下一个元素的引用(指针)组成。 这有点类似于一个火车,火车的每节车厢都装着...
  • 链表是线性表的一种,所谓的线性表包含顺序线性表和链表,顺序线性表是用数组实现的,在内存中有顺序排列,通过...而链表又包括单向链表、双向链表和循环链表,这篇文章主要学习单向链表和双向链表原理及其相关实现。
  • 图解Java数据结构之双向链表

    千次阅读 2019-08-08 13:39:46
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 增删改查思路...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,247
精华内容 19,298
关键字:

双向链表原理