精华内容
下载资源
问答
  • 当你想数组的任意位置,插入一个新值的时候,必须对数组的各个元素进行相应的位置移动才能达到目标,开销显然是很大的。然而链表的灵活性在于它的每个元素节点分为两部分,一部分是存储元素本身,另一部分是指向...

            链表是一种动态的数据结构,不同于数组的是,链表分配内存空间的灵活性,它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置,插入一个新值的时候,必须对数组中的各个元素进行相应的位置移动才能达到目标,开销显然是很大的。然而链表的灵活性在于它的每个元素节点分为两部分,一部分是存储元素本身,另一部分是指向下一个节点元素的引用,也可以称为指针,当你要插入数据时,把上一个节点的向下指针指向新数据节点,新数据节点的向下指针指向原有数据。但是链表不像数组那样可以直接通过索引立刻定位,只能通过遍历。 链表分配内存的动态性体现在内存的不连续性和无索引性,你可以随时随地增加或删除,如下图所示:

     在这里,我们定义了链表的五个操作:增加append,删除removeAt,插入insert,输出节点toString,以及索引indexOf。

    function LinkedList() {
        var Node = function (val) {       //新元素构造
            this.val = val;
            this.next = null;
        };
        var length = 0;
        var head = null;
    
        this.append = function (val) {
            var node = new Node(val);       //构造新的元素节点
            var current;
            if (head === null) {        //头节点为空时  当前结点作为头节点
                head = node;
            } else {
                current = head;              
                while (current.next) {     //遍历,直到节点的next为null时停止循环,当前节点为尾节点
                    current = current.next;
                }
                current.next = node;      //将尾节点指向新的元素,新元素作为尾节点
            }           
            length++;              //更新链表长度
        };
        this.removeAt = function (position) {
            if (position > -1 && position < length) {
                var current = head;
                var index = 0;
                var previous;
                if (position == 0) {
                    head = current.next;
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    previous.next = current.next;
                }
                length--;
                return current.val;
            } else {
                return null;
            }
        };
        this.insert = function (position, val) {
            if (position > -1 && position <= length) {   //校验边界
                var node = new Node(val);        
                current = head;
                var index = 0;
                var previous;
                if (position == 0) {       //作为头节点,将新节点的next指向原有的头节点。
                    node.next = current;
                    head = node;         //新节点赋值给头节点
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }               //遍历结束得到当前position所在的current节点,和上一个节点
                    previous.next = node;    //上一个节点的next指向新节点  新节点指向当前结点,可以参照上图来看
                    node.next = current;
                }
                length++;
                return true;
            } else {
                return false;
            }
        };
        this.toString = function () {
            var string = head.val;
            var current = head.next;        
            while (current) {
                string += ',' + current.val;
                current = current.next;
            }
            return string;
        };
        this.indexOf = function (val) {
            var current = head;
            var index = -1;
            while (current) {
                if (val === current.val) { //从头节点开始遍历
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;
        };
        this.getLength = function () {
            return length;
        }
        this.getHead = function () {
            return head;
        }
    }
    
    // 创建链表
    var li = new LinkedList();
    li.append(1);
    li.append(2);
    li.append(4);
    li.append(4);
    li.append(5);
    li.insert(2,3);
    li.insert(2,3);
    console.log(li.toString())  // 1,2,3,3,4,4,5
    console.log(li.getHead())   // 1->2->3->3->4->4->5

    参考:

    用JavaScript来实现链表LinkedList

    js创建链表

    END

    展开全文
  • 本文将来讲解一下种常见的线性数据结构链表,因为链表和数组一样都是种线性的数据结构,但是它俩的实现原理是完全不同的,所以讲解链表之前,我们来回顾一下 数组 结构。

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下数组结构。

    数组 几乎是每一种编程语言中都自带的一种常用的数据存储结构,我们可以很方便的通过下标值来获取到我们想要的数组中的元素。

    但是数组也还是有很大的缺点的,例如现在有一个长度为10的数组,那么数组中的每个元素都对应着各自的下标值,范围为 0~9 ,现在我们要往下标值为 2 的位置插入一个新的元素,我们需要做的就是先把数组的长度变成11,然后将数组中原本下标值为 2 以及之后的所有元素都向后移动一个位置,即下标值 +1,最后再将我们要插入的新元素放到下标值为 2 的位置。

    同样的,如果我们要删除数组中的某个元素,也是一样的道理,先删除要删除的元素,然后把被删除元素后面的所有元素往前移动一个位置,即下标值 -1,最后把数组的长度 -1

    由上面两个例子可以看出,数组的 添加元素删除元素 非常消耗性能,可谓牵一发而动全身,这就是数组最大的缺点,所以 链表 的出现就弥补了数组的这一缺点。本文就来详细讲解一下链表的概念以及如何实现一个链表。

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是链表

    上面刚提到,链表 弥补了数组的一些缺点,那么是如何做到的呢?链表到底是什么样的呢?接下来我们就用一个简单的例子来解释一下链表的概念

    假设在一个教室中,所有学生的座位都排成一列,这一列就可以看成是一个 链表,如图所示
    在这里插入图片描述
    每个座位上坐着的学生就相当于链表中的一个 元素 。假如老师记性不好,学生记性也不好,所以他们就很难记住自己的座位到底是哪一个。因此老师想了一个好办法,老师就只记住座位的第一个是谁,然后每一个学生都只要记住自己的后桌是谁就好了。

    每次刚进教室准备找座位坐下,老师就告诉学生们说,小5 是坐在第一个的,然后 小5 记得他的后桌是 小1,于是 小1 也找到了座位坐下,因为 小1 记得他的后桌是 小8,所以 小8 也找到自己的座位了……以此类推,一直到坐在最后一个的 小2,就这样大家就都可以找到自己的座位了,如图:
    在这里插入图片描述
    有一天, 小8 同学要转学了,所以座位有变动,为了保证座位不空着,小8 走了以后,把他的座位也搬走,以免占用教室空间。此时要让其余同学仍然能正确找到自己的座位的方式就很简单,那就是让原本 小8 的前桌记住,他现在的后桌是 小6了,不再是 小8 了,所以现在的情况如图所示:
    在这里插入图片描述
    像这样的记忆自己座位的方式非常的好,因为一个同学转学,只需要让一个人重新记忆自己的后桌是谁即可,而不需要让所有的同学重新记忆。

    同理,比如突然有一天,有一个新同学 小7 到了这个班级,老师安排她坐在 小5 后面,此时 小5 就需要记住,他的后桌换成了 小7,而这个新来的同学 小7 也像其他同学一样要记住自己的后桌为 小1,此时的情况是这样的,如图:
    在这里插入图片描述
    同样的,新来一个同学造成的位置变动,只让一个同学重新记忆自己的后桌是谁,还同时让新来的同学记住自己的后桌是谁,而没有让所有的同学全部重新记忆,这无疑是一个非常高效的方式。

    例子讲完了,接下来进入正题,链表 的实现就像我们刚才讲的那个例子。在链表中,每一个元素都包含两个属性,即 该元素的值item下一个元素next,其中,item 就像我们刚才例子中的同学;next 就像同学记住的他们的后桌是谁。同时链表中有一个指针 head 指向链表第一个元素,这个 head 就好比老师记住的坐在第一个的是谁。

    接下来我们来看一下链表的结构
    在这里插入图片描述
    这整体看上去就像一个链子,所以叫做链表,每一个 itemnext 组合起来称作是一个元素,再补充一下,最后一个元素指向 null,就相当于例子中坐在最后一个的同学说他没有后桌一样。

    此时我们要删除第二个元素,链表结构就会变成这个样子
    在这里插入图片描述
    大家可以根据这个结构比对一下刚刚我举得例子,好好理解一下链表的结构形式和实现原理。

    二、链表的方法

    因为链表是弥补数组缺点而形成的一种数据结构,所以链表也有像数组一样多的方法,这里我们就来看一下链表都有哪些方法吧

    方法含义
    append()向链表尾部追加元素
    insert()在链表的某个位置插入元素
    get()获取链表对应位置的元素
    indexOf()获取某元素在链表中的索引
    update()修改链表中某个位置上的元素的值
    removeAt()移除链表中某位置上的某元素
    remove()移除链表中的某元素
    isEmpty()判断链表内是否为空
    size()返回链表内元素个数
    toString()以字符串的形式展示链表内的所有元素

    三、用代码实现链表

    根据上面对链表的讲解,我们知道,我们无论是要删除元素还是添加元素,每次都是要从 head 开始,依次往后查找元素,所以对于链表的每一个方法,我们每次做的就是从 head 开始遍历,并通过 next 找到每一个元素的下一个元素是谁。

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放链表的一些属性和方法。

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    }
    

    其中定义了属性 head,并赋值了一个 null,表示现在链表内没有元素;而属性 length则是为了储存链表内的元素个数,这是为了提高链表一些方法的性能,例如之后要写的 size()方法,我们每次调用该方法时,都要遍历整个链表,然后统计元素个数,那么还不如有一个属性记录着元素个数,只需要在添加元素的方法里给 length + 1,在删除元素的方法里给 length - 1

    (2)创建内部构造函数

    链表的每一个元素都有两个属性,即 itemnext,分别表示存储着该元素的值和该元素的后一个元素是谁。所以我们就在链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    }
    

    之后要如果要添加新元素,我们只需要 new Node(item),并把元素的值传入就可以创建一个元素的实例对象了,这里默认是给每个新创建的元素实例的 next 属性设置为 null,是因为刚开始我们并不知道它被添加到链表里以后,后一个元素是谁,当然,我们只需要在知道了后一个元素是谁的情况下设置一下这个属性即可。

    (3)实现append()方法

    append()方法就是将元素添加到链表的最后一个。

    实现思路:

    1. 创建新的元素实例对象 node
    2. 判断 length 是否为0,若为0,则直接将 head 指向 node
    3. length 不为0,则根据每个元素的 next 属性遍历链表
    4. 若元素的 next 的值不等于 null,继续遍历
    5. 若元素的 next 的值等于 null,则表示已经查找到链表的最后一个元素,所以直接将该元素的 next 值设置成 node 即可
    6. 属性 length + 1

    为了方便你们理解这个实现思路,我做了个动图展示一下思路
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//在链表尾部追加元素
    	LinkedList.prototype.append = function (item) {
    		// 1.创建新的元素实例对象
            let node = new Node(item)
            
            // 2.判断链表是否为空
            if(this.length === 0) {
                this.head = node
            }
            else {
                let current = this.head
                // 3.遍历链表,找到最后一个元素
                while(current.next) {
                    current = current.next
                }
                // 4.将我们要添加的元素赋值给原本链表中的最后一个元素
                current.next = node
            }
    		
    		//链表元素+1
            this.length ++
        }
    }
    

    我们来使用一下该方法

    刚开始的链表是这个样子的
    在这里插入图片描述
    然后我们使用一下 append()方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    

    此时的链表是这样的
    在这里插入图片描述

    (4)实现insert()方法

    insert()方法就是在指定的索引位置插入元素。一共需要传入两个参数,第一个是 position,表示需要插入元素的位置;第二个参数是 item,表示元素的值

    实现思路:

    1. 创建新的元素实例对象 node
    2. 判断指定的索引位置 position 是否越界,即是否小于0,或者大于链表的长度。若越界了,则直接返回false
    3. 判断 position 是否为0。若为0,则直接将链表原本的第一个元素,也就是 head所对应的元素赋值给 nodenext属性,然后将 node赋值给 head,表示现在链表的第一个元素为 node
    4. position 不为0,则遍历链表,同时记录遍历的索引 index 和遍历的上一个元素 prev,当 index == position时,将链表在 index索引位置上的元素赋值给 nodenext属性,再将 node赋值给 prevnext属性
    5. 属性 length + 1

    为了方便你们理解这个实现思路,我做了个动图展示一下思路
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//在某个位置插入新的元素
        LinkedList.prototype.insert = function (position, item) {
        	// 1.创建新的元素实例对象
            let node = new Node(item)
            
    		// 2.判断是否越界
            if(position < 0 || position > this.length) return false
            
            // 3.判断插入的位置是否为 0
            if(position === 0) {
                node.next = this.head
                this.head = node
            }
            else {
            	// 4.遍历链表,找到索引等于position的元素
                let current = this.head
                let prev = null
                let index = 0
                while (index++ < position) {
                    prev = current
                    current = current.next
                }
        		// 5.插入元素
                prev.next = node
                node.next = current
        
            }
            // 6.链表元素 +1
            this.length ++
            return true
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.insert(1, 'c++')
    

    此时的链表是这样的
    在这里插入图片描述

    (5)实现get()方法

    get()方法就是获取对应位置上的元素。需要传入一个参数,即 position,表示需要获取元素的索引

    实现思路:

    1. 判断 position 是否越界。若越界,则直接返回false
    2. 遍历链表,同时记录当前索引 index,当 index == position时,返回当前位置上的元素

    接下来我们来单独实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//获取对应位置的元素
        LinkedList.prototype.get = function (position) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            
    	        let current = this.head
    	        let index = 0
    	        // 2.遍历链表,直到 index == position
    	        while (index++ < position) {
    	            current = current.next
    	        }
    	        // 3.返回当前索引位置的元素
    	        return current.item
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.get(2)            //返回 java
    

    (6)实现indexOf()方法

    indexOf()方法就跟数组的一样,获取某元素在链表中的索引值,若链表中不存在该元素,则返回 -1

    因为比较简单,这里就不讲解思路了,我们直接用代码来实现这个方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//获取元素的索引
        LinkedList.prototype.indexOf = function (item) {
            let current = this.head
            let index = 0
            while (index < this.length) {
                if(current.item === item) {
                    return index
                }
                else {
                    current = current.next
                    index ++
                }
            }
            return -1
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.indexOf('python')    //返回 1
    linkedlist.indexOf('c++')       //返回 -1
    

    (7)实现update()方法

    update()方法就是用于修改链表中某位置上的元素的值。因此该方法需要传入两个参数,第一个参数是 position,表示需要修改的元素的索引;第二个参数是 NewItem,表示修改后的值

    这里就简单讲下思路吧,首先要先判断 position 是否越界,若越界直接返回 false表示修改失败,若没有越界就遍历链表,同时记录当前索引 index,当 index == position时,就将当前索引位置上的元素的值 item修改成 NewItem

    接下来我们来单独实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//修改某位置上的元素
        LinkedList.prototype.update = function (position, NewItem) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            else {
                let current = this.head
                let index = 0
                
                // 2.遍历链表,找到索引等于position的元素对象
                while (index < position) {
                    current = current.next
                    index ++
                }
                
                // 3.将索引等于position的元素的值改为NewItem
                current.item = NewItem
                return true
            }
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.update(2, 'c++') 
    

    此时的链表是这样的
    在这里插入图片描述

    (8)实现removeAt()方法

    removeAt()方法就是用于移除链表中某位置上的某元素。该方法只需要传入一个参数 position,表示需要移除元素的索引

    实现思路:

    1. 判断 position 是否越界,若越界,则直接返回 false 表示移除元素失败
    2. 若没有越界,判断 position 是否等于 0,若等于 0,则直接将链表第一个元素的 next 值赋值给 head,然后 length - 1
    3. position 不等于 0,则遍历链表,同时记录当前索引 index,遍历的当前元素 currentcurrent的上一个元素 prev
    4. index === position时,则将 currentnext 值赋值给 prevnext 值即可,同时 length - 1

    为了让大家更好地理解该方法的实现思路,我制作了一个动图来帮助大家理解,如图
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//移除某位置上的元素
        LinkedList.prototype.removeAt = function (position) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            
            let current = this.head
            let prev = null
            let index = 0
            
            // 2.判断position是否等于 0
            if(position === 0) {
                this.head = current.next
            }
            else {
            	// 3.遍历链表
                while (index < position) {
                    prev = current
                    current = current.next
                    index ++
                }
                // 4.移除对应元素
                prev.next = current.next
            }
    		
    		// 5.链表元素 -1
            this.length --
            return true
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.removeAt(2)    //返回  true
    linkedlist.removeAt(3)    //返回  false,表示删除失败
    

    此时的链表是这样的
    在这里插入图片描述

    (9)实现remove()方法

    remove()方法就是用于移除链表中的某元素,并返回被删除元素所在的索引位置,若链表中没有对应元素,则返回 false 。该方法需要传入一个参数 data用于查找链表中对应的元素

    实现思路:

    1. 利用上面封装的 indexOf()方法,将 data 作为参数传入,获取到 data 在链表中的索引 index
    2. 再利用上面封装的 removeAt()方法,将 index 作为参数传入,就可以实现 remove()方法的功能了。

    我们简单来写一下代码实现该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//移除某元素
        LinkedList.prototype.remove = function (data) {
        	// 1.获取data在链表中的索引
            let index = this.indexOf(data)
    		
    		// 2.利用removeAt()方法删除链表中的data
            this.removeAt(index)
    		
    		// 3.返回被删除元素data在链表中的索引
    		return index
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.remove('javascript')    //返回 0
    

    此时链表是这个样子的
    在这里插入图片描述

    (10)实现isEmpty()方法

    isEmpty()方法就是判断链表中是否有元素。若有元素,则返回 false;反之,返回 true

    该方法的实现思路很简单,直接判断属性 length 是否等于 0 就可以了。

    话不多说,我们赶紧写代码实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//判断链表是否为空
        LinkedList.prototype.isEmpty = function () {
            if(this.length === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.isEmpty()          //返回 true,此时链表中无元素
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.inEmpty()         //返回 false,此时链表中有三个元素
    

    (11)实现size()方法

    szie()方法就是返回链表内的元素个数

    我们来实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//返回链表的元素个数
        LinkedList.prototype.size = function () {
            return this.length
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.size()          //返回 0,此时链表中无元素
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.size()         //返回 3,此时链表中有三个元素
    

    (12)实现toString()方法

    toString()方法就是以字符串的形式展示链表内的所有元素

    实现思路很简单,就是遍历链表中的每一个元素,并将每个元素以字符串的形式连接起来即可

    我们来实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//展示整个链表
        LinkedList.prototype.toString = function () {
            let string = ''
            let current = this.head
            while (current) {
                string += `${current.item} `
                current = current.next
            }
            return string
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.toString()           //返回 javascript python java
    

    四、总结

    链表结构的讲解就到这里了,希望大家对链表有了更深一层的理解。下一篇文章我将讲解一下另一种链表结构,叫做双向链表

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历...数据结构——双向链表一、什么是双向链表二

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历结构内的元素,那么双向链表就是既可以从头开始遍历,又可以从结构的末尾开始遍历。

    上一篇文章的跳转链接——【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

    本文就来详细讲解一下双向链表的概念以及如何实现一个双向链表。

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是双向链表

    在上一篇文章中,我们用一个生活中的例子来解释了链表的概念,那么本文就延用这个例子,并对该例子做一些改动,来解释什么是 双向链表

    我们来看一下这个例子:

    在一个教室里,所有的课桌排成一列,如图
    在这里插入图片描述
    相信在你们的读书生涯中,老师肯定有要求你们记住自己的前后桌是谁。所以该例子中,老师就要求学生们记住自己的前后桌,其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁;最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图:
    在这里插入图片描述
    这一列座位就相当于一个 双向链表。

    假如有一天,老师还没记住每个学生的名字,于是就问:这一列第三个人叫什么名字?这时就要从第一个学生开始数,例如从图中坐在第一个的 小5 开始数:第一个人是 小5,他的后桌是 小7;因此第二个人就是 小7,他的后桌是 小1;因此第三个人就是 小1 了。此时老师问 小1:你的前桌叫什么名字?你的后桌叫什么名字?

    因为刚开始老师就让每个学生记住了自己的前桌以及后桌,所以此时 小1 能很快地告诉老师他的前桌是 小7,他的后桌是 小6

    但是,我们设想一下,如果是上一篇文章的 链表结构 的例子中,如果老师在得知了第三个人是 小1 以后,询问 小1 的前桌叫什么名字,小1 能回答上来吗?并不能,因为老师只让每个学生记住了自己的后桌,所以此时想要得知 小1 的前桌叫什么名字,只能这样:第三个学生叫 小1,那么他的前桌就坐在第二个位置,所以从第一个学生开始数,第一个学生是 小5,他的后桌是 小7;因此第二个学生就是 小7。当然本文举得例子中学生数量有点少,但一旦数量多起来了,每次问一个学生他的前桌叫什么名字的时候,都要从头开始数。

    从中可以看出,让每个学生记住自己的前桌后桌是非常有必要的,因为在某些情况下,可以快速地解决问题。

    上面讲了那么多,接下来我们就来看一下 双向链表 是什么样的,如图
    在这里插入图片描述
    可以看到,对比 链表结构双向链表 多了一个指针 tail,它是指向最后一个元素的,就相当于例子中的学生记住了自己是最后一排。

    二、双向链表的方法

    因为 双向链表 是链表的一种特殊形式,所以这两者的常用方法也是一样的,只不过实现方式不一样,那么我再列举一下有哪些常用方法吧,如下表

    方法含义
    append()向双向链表尾部追加元素
    insert()在双向链表的某个位置插入元素
    get()获取双向链表对应位置的元素
    indexOf()获取某元素在双向链表中的索引
    update()修改双向链表中某个位置上的元素的值
    removeAt()移除双向链表中某位置上的某元素
    remove()移除双向链表中的某元素
    isEmpty()判断双向链表内是否为空
    size()返回双向链表内元素个数
    toString()以字符串的形式展示双向链表内的所有元素

    接下来就用 JavaScript 来实现一下以上这些方法

    三、用代码实现双向链表

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放双向链表的一些属性和方法。

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    }
    

    其中,属性 head 表示双向链表中的第一个元素;属性 tail 表示双向链表中的最后一个元素

    (2)创建内部构造函数

    双向链表的每一个元素都有三个属性,即previtemnext,分别表示该元素的前一个元素是谁 、存储着该元素的值和该元素的后一个元素是谁。所以我们就在双向链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    }
    

    (3)实现append()方法

    append()方法就是将元素添加到双向链表的末尾。

    实现思路:

    1. 先创建新元素的实例对象 node
    2. 先判断双向链表内有无元素,若没有元素,则将属性 head 和 属性 tail 都指向 node,最后属性 length + 1
    3. 若双向链表中有元素了,则因为双向链表内多了一个指针 tail,所以我们要实现 append()方法也就方便了很多,只需要将 tail 指向 node,然后将原本的末尾元素 old_nodenext 指向 node,并将 nodeprev属性指向 old_node即可,然后属性 length + 1

    为了方便大家理解,我用一个动图来向大家演示一下:
    在这里插入图片描述
    在这里插入图片描述

    思路讲解完了,我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//在末尾加入元素
        DoubleLinkedList.prototype.append = function (item) {
        	// 1.创建新元素的实例对象
            let node = new Node(item)
    		
    		// 2.判断双向链表内是否有元素
            if(this.length === 0) {
                this.head = node
                this.tail = node
            }
            else {
                node.prev = this.tail
                this.tail.next = node
                this.tail = node
            }
    		
    		// 3. 双向链表内元素 + 1
            this.length ++
        }
    }
    

    接下里我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('js')
    dl.append('python')
    

    此时的链表内是这样的
    在这里插入图片描述

    (4)实现insert()方法

    insert()方法就是在指定的索引位置插入元素。一共需要传入两个参数,第一个是 position,表示需要插入元素的位置;第二个参数是 item,表示元素的值

    实现思路:

    1. 创建新的元素实例对象 node
    2. 判断指定的索引位置 position 是否越界,即是否小于0,或者大于双向链表的长度。若越界了,则直接返回false
    3. 判断 position 是否为0。若为0,则直接将双向链表原本的第一个元素 ,也就是 head所对应的元素 old_node 赋值给 nodenext属性,再将 node 赋值给 old_nodeprev 属性,然后将 node赋值给 head,表示现在链表的第一个元素为 node
    4. position 不为0,则遍历双向链表,同时记录遍历的索引 index 、遍历的上一个元素 prev 和在 index索引位置上的元素 current,当 index == position时,将 node赋值给 prevnext属性,将 current 赋值给 nodenext属性,再将 prev 赋值给 nodeprev 属性,最后将 node 赋值给 currentprev 属性
    5. 属性 length + 1

    为了方便大家理解,我用一个动图来向大家演示一下:
    在这里插入图片描述
    在这里插入图片描述
    看完了方法的实现思路,我们来用代码实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//向指定位置插入元素
        DoubleLinkedList.prototype.insert = function (position, item) {
            // 1.判断是否越界
            if(position < 0 || position > this.length) {
                return false
            }
            // 2.创建新元素的实例对象
            let node = new Node(item)
            let index = 0
            let current = this.head
            let prev = null
            
            // 3.判断插入位置是否等于元素个数
            if(position === this.length) {
            	//当 position 与 length相等时,就相当于在末尾添加元素
                this.append(item)
            }
    
    		// 4. 判断元素是否添加到第一个位置
            else if(position === 0) {
                node.next = this.head
                this.head.prev = node
                this.head = node
                this.length ++
            }
            else {
            	// 5.遍历链表,直到找到position位置上的元素
                while (index < position) {
                    prev = current
                    current = current.next
                    index ++
                }
                // 6.插入新元素
                prev.next = node
                current.prev = node
                node.prev = prev
                node.next = current
                this.length ++
            }
        }
    }
    

    接下来我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.insert(0, 'C++')
    

    此时的双向链表是这样的
    在这里插入图片描述
    在执行一次 insert()方法

    di.append('js')              //在末尾添加元素 js
    dl.insert(1, 'python')       //在索引 1处插入元素python
    

    此时的双向链表是这样的
    在这里插入图片描述
    最后我们再向索引为 3 的位置插入元素 java,因为此时 length = 3,即双向链表元素个数为 3,这就相当于在末尾添加元素

    dl.insert(3, 'java')
    

    所以此时的链表是这样的
    在这里插入图片描述

    (5)实现get()方法

    get()方法就是获取对应位置上的元素。需要传入一个参数,即 position,表示需要获取元素的索引

    实现思路:

    1. 判断 position 是否越界。若越界,则直接返回false
    2. 遍历链表,同时记录当前索引 index,当 index == position时,返回当前位置上的元素

    该方法思路比较简单,几乎跟链表的 get()方法一样,我们来看一下

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//获取对应位置上的元素
        DoubleLinkedList.prototype.get = function (position) {
            if(position < 0 || position > this.length - 1) {
                return false
            }
            let index = 0
            let current = this.head
            while (index < position) {
                current = current.next
                index ++
            }
            return current.item
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.get(-2)           //返回 false
    dl.get(0)            //返回 C++
    dl.get(2)            //返回 python
    dl.get(3)            //返回 false
    

    (6)实现indexOf()方法

    indexOf()方法就跟数组的一样,获取某元素在双向链表中的索引值,若双向链表中不存在该元素,则返回 -1

    这个方法思路很简单,就不详细讲解了,直接来看代码

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//获取元素的索引
        DoubleLinkedList.prototype.indexOf = function (item) {
            let current = this.head
            let index = 0
            
            // 1.遍历双向链表
            while (index < this.length) {
            	// 2. 找到对应元素,返回索引值
                if(current.item === item) {
                    return index
                }
                else {
                    index ++
                    current = current.next
                }
            }
            // 3.未找到对应元素,返回 -1
            return -1
    
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.indexOf('C++')           //返回 0
    dl.indexOf('js')            //返回 1
    dl.indexOf('python')        //返回 2
    dl.indexOf('java')          //返回 -1
    

    (7)实现update()方法

    update()方法就是用于修改双向链表中某位置上的元素的值。因此该方法需要传入两个参数,第一个参数是 position,表示需要修改的元素的索引;第二个参数是 NewItem,表示修改后的值

    该方法的实现思路跟普通链表一模一样,所以就不讲解具体的实现思路了,直接来看代码吧

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//修改某位置上的元素
        DoubleLinkedList.prototype.update = function (position, item) {
        	
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) {
                return false
            }
            let index = 0
            let current = this.head
            
            // 2.遍历双向链表,直到找到对应位置上的元素
            while (index < position) {
                index ++
                current = current.next
            }
            // 3.修改position索引位置上的元素的值
            current.item = item
            return true
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    

    此时的链表是这样的
    在这里插入图片描述
    现在调用一下 update()方法,修改索引位置为 2 的元素的值

    dl.update(2, 'java')
    

    此时的链表是这样的
    在这里插入图片描述

    (8)实现removeAt()方法

    removeAt()方法就是用于移除双向链表中某位置上的某元素。该方法只需要传入一个参数 position,表示需要移除元素的索引

    实现思路:

    1. 先判断 position 是否越界,若越界了,则直接返回 false 表示移除元素失败
    2. 若没有越界,则判断 position 是否为 0,若等于 0,则直接将第一个链表的 next 值赋值给 head,然后 length - 1
    3. position 不等于 0而等于 length - 1,则将末尾元素的前一个元素,即 tailprev对应的元素的 next 属性设置成 null,并将 tail 指向当前 tailprev,最后 length - 1
    4. position 既不等于 0,又不等于 length - 1,则遍历双向链表,同时记录当前索引 index,遍历的当前元素 currentcurrent的上一个元素 prev
    5. index === position时,将 current 的下一个元素,即 currentnext 属性值赋值给 prevnext 属性,同时将 current 的下一个元素的 prevprev 属性设置成 prev,最后 length - 1

    为了让大家更好地理解该方法的实现思路,我制作了一个动图来帮助大家理解,如图
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//移除某位置上的元素
        DoubleLinkedList.prototype.removeAt = function (position) {
            // 1.判断是否越界
            if(position < 0 || position >= this.length) {
                return false
            }
            
            // 2.判断清除的元素是否为链表的唯一元素
            if(position === 0 && position === this.length - 1) {
                this.head = null
                this.tail = null
            }
            // 3.判断清除的元素是否为链表的第一个元素
            else if(position === 0) {
                this.head.next.prev = null
                this.head = this.head.next
            }
            // 4.判断清除的元素是否为链表的最后一个元素
            else if(position === this.length - 1) {
                this.tail.prev.next = null
                this.tail = this.tail.prev
            }
            else {
                let current = this.head
                let prev = null
                let index = 0
                // 5.遍历双向链表
                while (index < position) {
                    index ++
                    prev = current
                    current = current.next
                }
                // 6.删除对应位置上的元素
                prev.next = current.next
                current.next.prev = prev
            }
            // 7.元素个数 - 1
            this.length --
            return true
    
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.removeAt(2)         //删除索引为 2位置上的元素
    

    此时的双向链表是这样的
    在这里插入图片描述

    (9)实现remove()方法

    remove()方法就是用于移除双向链表链表中的某元素,并返回被删除元素所在的索引位置,若链表中没有对应元素,则返回 false 。该方法需要传入一个参数 data用于查找链表中对应的元素

    实现思路:

    1. 利用上面封装的 indexOf()方法,将 data 作为参数传入,获取到 data 在链表中的索引 index
    2. 再利用上面封装的 removeAt()方法,将 index 作为参数传入,就可以实现 remove()方法的功能了。

    我们简单来写一下代码实现该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//移除某元素
        DoubleLinkedList.prototype.remove = function (data) {
        	// 1.获取data在双向链表中的索引
            let index = this.indexOf(data)
    		
    		// 2.利用removeAt()方法删除双向链表中的data
            this.removeAt(index)
            
            // 3.返回被删除元素data在双向链表中的索引
            return index
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.remove('js')            //返回 1,此时length = 2
    dl.remove('python')        //返回 1,此时length = 1
    

    此时的链表是这样的
    在这里插入图片描述

    (10)实现isEmpty()方法

    isEmpty()方法就是判断双向链表中是否有元素。若有元素,则返回 false;反之,返回 true

    该方法的实现思路很简单,直接判断属性 length 是否等于 0 就可以了。

    话不多说,我们赶紧写代码实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//判断双向链表是否为空
        DoubleLinkedList.prototype.isEmpty = function () {
            if(this.length === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.isEmpty()             //返回 true,此时双向链表中无元素
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.isEmpty()             //返回 false,此时双向链表中有3个元素
    

    (11)实现size()方法

    szie()方法就是返回链表内的元素个数

    我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//返回双向链表元素个数
        DoubleLinkedList.prototype.size = function () {
            return this.length
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.size()             //返回 0,此时双向链表中无元素
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.size()             //返回 3,此时双向链表中有3个元素
    

    (12)实现toString()方法

    toString()方法就是以字符串的形式展示双向链表内的所有元素

    实现思路很简单,就是遍历双向链表中的每一个元素,并将每个元素以字符串的形式连接起来即可

    我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//展示双向链表数据
        DoubleLinkedList.prototype.toString = function () {
            let current = this.head
            let string = ''
            while (current) {
                string += current.item + ' '
                current = current.next
            }
            return string
        }
    }
    

    四、双向链表的补充

    其实平常的时候 双向链表 的应用场景比较多,而且它某些时候比普通的链表数据操作的效率要高。

    例如:假设有一个 length = 9999 的普通链表,我们要删除该链表索引为 9997 的元素,那么我们只能从链表的第一个元素,即从 head 指向的元素开始遍历链表,直到找到索引为 9997 的元素,一共要遍历9998次,这样效率是非常低的。

    那么如果把普通链表换成双向链表呢?当我们得知要删除索引为 9997 的元素时,我们可以先计算 99979999 - 1 = 9998 的差值 、99970 的差值,若前者差值小,则可以从双向链表的 tail 指向的元素往前遍历;反之,从 head 指向的元素往后遍历。如图
    在这里插入图片描述

    五、总结

    双向链表的讲解就到这里了,希望大家对双向链表有了更深一层的理解。下一篇文章我将讲解一下哈希表

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • C语言数据结构-链表创建

    千次阅读 多人点赞 2019-02-22 21:30:58
    1.结点结构 typedef int datatype; ... 每创建一个结点,都使该结点成为头结点,这样头结点不断地向前移动,就可以创建一个没有特定头结点的链表。  首先创建的结点,会出现整个链表的最...

    1.结点结构

    typedef int datatype;
    
    typedef struct Node{
    
      datatype data;
    
      struct NODE *next;
    
    }Node,*LinkList;
    

    2.不带头结点的头插法

      每创建一个结点,都使该结点成为头结点,这样头结点不断地向前移动,就可以创建一个没有特定头结点的链表。

      首先创建的结点,会出现在整个链表的最末端,所以数据的写入是逆序的。

      注意:开始的时候,head要初始化为NULL

    LinkList LinkListCreate(int n)
    {
        int i;
        LinkList head;
        Node *p;
        head = NULL;
        for(;i<n;i++)
        {
            p = (Node*)malloc(sizeof(Node));
            if(NULL == p)
                perror("ERROR");
         scanf("%d",&p->data);
            p->next = head;
            head = p;
        }
    }

    3.不带头结点的尾插法创建链表

      指向头结点的指针不能移动,要创建一个一直指向尾结点的指针rear。

    LinkList LinkListCreate(int n)
    {
        int n= 0;
        LinkList head;
        Node *p,*rear;
        rear = head = NULL;
        for(;i<n;i++)
        {
            p = (Node*)malloc(sizeof(Node));
            scanf("%d",&p->data);
    
            if(NULL == head)
            else rear->next = p;
    
            rear = p;
        }
       rear->next = NULL;
    }

    注意:最后设置链表的结尾为NULL

    4.头结点

    头结点的数据域可以不存储任何信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。头结点的作用是使所有链表(包括空表)的头指针非空,并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行,从而与其他位置的插入、删除操作一致。

    5.带结点的头插法创建链表

     LinkList LinkListCreate(int n)
     {
         int i = 0;LinkList p;
         LinkList head = (Node*)malloc(sizeof(Node));
         head->next = NULL;
         
         for(;i<n;i++)
         {
             p = (Node*)malloc(sizeof(Node));
             scanf("%d",&p->data);
             p->next = head->next;
             head->next = p;
         }
          return head;
    }

    6.带结点的尾插法创建链表

    LinkList LinkListCreate(int n)
    {
        //开始创建的时候,rear = head.  rear->next = p; rear = p
        //最后要使的rear->next = NULL;
    
        int i = 0;Node *p,*rear;
        LinkList head = (Node*)malloc(sizeof(Node));
        rear = head;
        
        for(;i<n;i++)
        {
            p = (Node*)malloc(sizeof(Node));
            scanf("%d",&p->data);
    
            rear->next = p; 
            rear = p;
        }
        rear->next = NULL;
    
        return head;
    }

    7.头结点两个优点

    (1)由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上

          的操作一致,无需进行特殊处理;

     (2)无论链表是否为空,其头指针是指向头结点在的非空指针(空表中头结点的指针域为空),因此空表和

         非空表的处理也就统一了。

    基于上述两点优点,创建带头结点的链表会更好

     

     

     

     

     

     

     

    展开全文
  • //将两个有序链表并为一个有序链表算法,该程序也可以cFree环境运行。 // c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> // malloc()等 #include<limits.h> //...
  • 数据结构 链表 插入一个节点

    千次阅读 多人点赞 2020-07-06 15:46:49
    链表 插入一个节点 经典举例 如图:共有四个节点,将第四个节点插入到①②之间。定义了指针向量p指向第一个节点,指针向量q指向节点④ 定义的节点的数据类型如下: //节点的数据类型 typedef struct Node { int ...
  • 步骤分析 分析: 创建链表一个从无到有... 在链表中去找到第一个比待插入元素值大的结点 比较, 那么比较节点的前面就是插入位置 1.当链表上所有结点的值,都比待插入元素要小,待插入元素是老大 =&gt;...
  • 创建一个python链表

    2020-06-12 09:34:33
    python3创建链表的过程可以粗略分为定义单节点,定义空链表,向空链表填充数据步骤 (来自https://www.educative.io/edpresso/how-to-create-a-linked-list-in-python) 定义单节点: class Node: # ...
  • 数据结构之双链表

    千次阅读 多人点赞 2021-08-04 18:59:48
    链表结构图示项目的建造双链表结点的定义双链表的各种方法实现双链表之新建结点双链表之初始化双链表之判链表之求具体元素数量双链表之打印链表内容双链表之尾插双链表之尾删双链表之头插双链表之头删双链表...
  • 1.首先创建一个空链表结构体struct listnode { //链表成员的结构体,含有节点和指针,而链表的第一个成员称为头节点和头指针 int value; //节点 其中头节点的数据可以为空 listnode* next; //指向下一个链表成员的...
  • C++:数据结构-链表创建

    千次阅读 2019-03-20 14:03:30
    链表的概念就不多说了,上一次用Java实现了链表这次用C++,来对比一下区别。链表介绍及JAVA实现 C++链表连接的理解 ...最后让head指向自己的下一个结点,因为head当前是的,尾结点p指向 借图理解...
  • 数据结构链表创建和打印

    千次阅读 2017-02-27 20:41:43
    #include "stdafx.h" struct node { int num; struct node *next;...//创建链表 struct node * creat() { struct node *head, *temp, *newp;//分别表示头节点、中间节点、新节点 int n;//节点数据 head = temp =
  • 数据结构】合并两有序链表

    千次阅读 2018-07-31 16:11:51
    链表面试题2:输入两递增排序的链表,合并这两个链表并使新链表的结点仍然是按照递增排序的。 分析题目:根据题目可模拟画出如下示意图,须将链表1和链表2合并并排序为链表3 解题思路: 1、先找出...
  • 我们知道,在数据结构中链表一般有两个部分:data以及指针域next。 那么怎么通过data以及next创建一个链表呢? 万物皆有开端,所以我们首先需要创立一个头结点,head。 public static Node createLinkByHead(Scanner...
  • 怎样一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表) /* 6.怎样一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表)? */ ListNode* ReverseList(ListNode* head) { if...
  • C++数据结构——链表

    千次阅读 2018-06-27 22:03:59
    C++数据结构——链表参考博客:(1)实践:https://www.cnblogs.com/renyuan/archive/2013/05/21/3091524.html(2)实践:https://blog.csdn.net/lg1259156776/article/details/47021505(3)理论:数据结构(二)...
  • 数据结构 - 链表

    千次阅读 2020-06-16 22:12:20
    线性表的链式存储结构 - 链表
  • C语言 链表(一) 创建一个简单的链表

    千次阅读 2020-11-27 10:30:31
    C语言 创建一个简单的链表 个人C语言学习之路(欢迎交流,相互学习): 用面向对象的思维,更规范地使用C语言。 ->首先我们定义了一个链表的结构体 ->里面简单封装了链表自身的属性(存放的数据,指向下一个...
  • 数据结构空链表的建立

    千次阅读 2014-08-14 09:10:25
    由此可以 #define Listsize 100 #define Listincrement 10 typedef struct {  Elemtype *elem;  int length;  int listsize;  }SqList; Status InitList_Sq(SqList &L) ...{//构建一个空链表  
  • 图解Java数据结构之环形链表

    千次阅读 2019-08-08 15:01:38
    本篇文章介绍数据结构中的环形链表。 介绍 环形链表,类似于单链表,也是一种链式存储结构,环形链表由单链表演化过来。单链表的最后一个结点的链域指向NULL,而环形链表的建立,不要专门的头结点,让最后一个结点的...
  • 数据结构 线性结构篇——链表

    千次阅读 多人点赞 2019-11-30 14:38:23
    一、前言 前面两章我们讲解了...但是我们今天要讲解的 链表 不一样,链表 是我们数据结构学习的一个重点,也有可能是一个难点,为什么链表这么重要呢?因为他是最简单的也是 真正的动态数据结构。 二、为什么链...
  • 数据结构 - 链表 - 面试常见的链表算法题 数据结构是面试必定考查的知识点,面试者需要掌握几种经典的数据结构:线性表(数组、链表)、栈与队列、树(二叉树、二叉查找树、平衡二叉树、红黑树)、图。 本文...
  • 数据结构链表详解

    千次阅读 多人点赞 2019-03-18 13:38:11
    文章目录链表链表数组和链表的对比手写一个链表链表设立虚拟头结点链表的遍历,查询和修改链表元素的删除链表的时间复杂度分析使用链表实现栈使用链表实现队列 链表 动态数组、栈、队列都是底层依托静态数组,靠...
  • 将单链表终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环。这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list) 循环链表带有头结点的空链表 非空的循环链表 其实...
  • 数据结构复习】链表

    千次阅读 多人点赞 2021-01-28 14:53:30
    所有图片来自数据结构与算法基础(青岛大学-王卓)的PPT,顺便安利波,老师的课讲的很好,墙裂推荐! 链表 单链表 定义: 基础操作 初始化 判断链表是否为空 空链表:链表无元素。(头指针和头结点仍) 判断...
  • 接上一篇内容,这次使用尾插法来创建单链表: ...2.然后下面就是通过尾插法创建单链表的程序,这里面稍稍要去理解的是通过一个指针来标记新的头节点的方法:listnode CreatlistTail(listnode* L, int a[], int len) {
  • 双向链表——删除两双向链表中相同的节点。
  • 数据结构和算法03】链表

    千次阅读 多人点赞 2016-04-12 20:29:44
    况且一个数组创建后,它的大小是无法改变的。 本章中,我们将讨论下链表这个数据结构,它可以解决上面的一些问题。链表可能是继数组之后第二种使用得最广泛的通用数据结构了。本章主要讨论单链表和双向链表。 ....
  • 图解链表:● 建立动态链表 待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向 1.任务是开辟结点和输入数据 2.并建立前后相链的关系p1重复申请...2.每访问一个结点,就将当前指针向该结点的下一个
  • :malloc申请动态空间注意以下事项: 1,malloc申请动态空间时必须声明类型; 2,使用malloc申请的空间使用完成之后必须使用free释放; 3,malloc申请空间的类型必须和指向他的指针类型匹配;such as: int *p; p=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 224,625
精华内容 89,850
关键字:

在数据结构中怎样创建一个空链表

数据结构 订阅