单向链表 订阅
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。 展开全文
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。
信息
外文名
One-way LinkedList
定    义
链表的一种
特    点
链表的链接方向是单向的
中文名
单向链表
目    的
学习单向链表
单向链表链表的优点
相比较普通的线性结构,链表结构的可以总结一下: (1)单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小(2)结点的删除非常方便,不需要像线性结构那样移动剩下的数据(3)结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表
收起全文
精华内容
下载资源
问答
  • 1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
  • C/C++实现单向链表

    2019-01-16 14:21:10
    分别用C和C++实现了单向链表(创建链表,插入数据、获取指定位置的数据、删除指定位置的数据...),如果在使用中觉得api不够用可以进行扩展;其中包含测试。
  • 单向链表 代码架构

    2018-12-29 09:07:41
    单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
  • c#单向链表的实现

    2017-12-20 18:55:29
    c#单向链表的实现,帮助大家学习,程序完全可以运行,
  • 04.单向链表以及单向链表的应用.ppt
  • C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。 链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的...
  • 主要介绍了Python单向链表和双向链表原理与用法,结合实例形式详细分析了单向链表与双向链表的概念、原理以及创建、添加、删除等相关操作技巧,需要的朋友可以参考下
  • 栈是基本的数据结构。其特点是添加和访问数据都在线性表的一端(头端)。数据访问遵循先进后出(FILO)的原则。...本程序用单向链表实现栈。是C++、数据结构及算法学习的一个小小练习。供大家参考。
  • C++单向链表.rar

    2019-10-19 17:57:08
    这是近期自己参考书上和网上资源使用C++编的单向链表,主要包含了链表的增删改查功能,除此之外还有简单的排序功能,代码实现的效果图已经在项目文件夹中了,可以按照效果图进行数据的增删改查等操作,最后也希望对...
  • C++实现简单单向链表

    2020-12-17 18:29:59
    本文实例为大家分享了C++实现简单单向链表的具体代码,供大家参考,具体内容如下 为了练习一下对链表的理解,尝试手动造轮子,实现单向链表的右添加,左添加和删除的功能。 头文件 #pragma once #include using ...
  • java单向链表的实现实例。需要的朋友可以过来参考下,希望对大家有所帮助
  • 今天小编就为大家分享一篇关于数据结构与算法:单向链表实现与封装,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 含单链表类LinkList.h, 结点类Node.h, 辅助头文件Assistance.h, 测试文件TestLinkList.cpp及TestLinkList.exe
  • 单向链表实现基排序

    2017-04-08 02:41:37
    利用单链表实现基排序算法
  • 使用C语言实现了单向链表的创建,输出,插入元素和删除元素以及单向链表的逆序连接和两个有序线性表的归并
  • 主要给大家介绍了关于Java实现单向链表基本功能的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。
  • 使用给定数据结构,实现带头结点的单向链表的创建、删除链表、插入结点等操作,每个学生的学号互不相同,学号不同而姓名相同则为不同的学生,每个学生的学号在合并后的链表中不重复,如果出现重复,则删除年龄较小...
  • 主要介绍了python实现单向链表详解,分享了相关代码示例,每一步操作前都有简单分析,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
  • 下面小编就为大家带来一篇python数据结构链表之单向链表(实例讲解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 有关单向链表的增删改查,对于单向链表的插入,在固定节点后面插入分为四种情况
  • 单向链表实现

    2017-04-08 02:39:02
    本源代码详细介绍单向链表的创建和使用
  • 本文实例讲述了python实现获取单向链表倒数第k个结点的值。分享给大家供大家参考,具体如下: #初始化链表的结点 class Node(): def __init__(self,item): self.item = item self.next = None #传入头结点,获取...
  • NULL 博文链接:https://chaoyi.iteye.com/blog/2078088
  • 源码包含单向链表和双向链表,注释比较详细,简单明白,适合新手初学者下载使用,比较基础。觉得有用记得收藏哦!
  • 单向链表的C语言实现

    2017-11-07 20:32:28
    C语言指针实现单向链表 初学者看,非常简单。 时间非常多的功能不同位置的插入、删除、查找;
  • c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
  • Python实现单向链表

    2020-02-02 16:16:11
    Python实现单向链表 关于链表的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/104033254 本篇文章使用 Python 来实现一个单向链表。 一、定义一个创建节点的类 链表是由一个个的节点...

    Python实现单向链表

    关于链表的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/104033254

    本篇文章使用 Python 来实现一个单向链表。

    一、定义一个创建节点的类

    链表是由一个个的节点组成的,在创建链表之前,要先创建节点,然后把节点“串”到链表上。在同一个链表中,每个节点的结构都相同,只是节点中保存的数据不同和引用不同,所以提前声明一个创建节点的类,需要创建节点时实例化即可。

    # coding=utf-8
    class Node(object):
    
        def __init__(self, data):
            self.data = data
            self.next = None

    单向链表的节点包含两个域,一个信息域(元素域)和一个链接域(引用域)。在实例化一个节点时,需要传入该节点中保存的数据,保存到信息域中,链接域默认为空,当对节点进行“链接”操作时,再设置具体的链接域。

    二、定义一个单向链表类

    对于单向链表,在没有将节点“链接”上去时,这个链表里没有节点和数据。实例化一个单向链表时,这个单向链表是一个空链表,把节点依次“链接”上去后,链表中才有节点和数据。

    在链表中,要找到链表的某个节点,需要从链表的头节点开始,依次寻找,所以在实例化一个链表时,必须定义好链表的“头”,当加入头节点时,将链表的“头”指向头节点。

    定义一个单向链表类 SingleLinkList,初始化一个单向链表时,链表的“头”指向空值,默认为空链表。

    class SingleLinkList(object):
    
        def __init__(self):
            self.__head = None

    三、实现单向链表的展示功能

        def is_empty(self):
            return not self.__head
    
        def show(self):
            if self.is_empty():
                print('空链表')
                return
            cur = self.__head
            while cur is not None:
                if cur.next is not None:
                    print(cur.data, end=' → ')
                else:
                    print(cur.data)
                cur = cur.next

    先实现判断单向链表是否为空的方法 is_empty() ,实例化单向链表时,默认是空的,单向链表的头指向为空。所以,如果单向链表的头指向为空(对应布尔值False), is_empty() 的值就为 True ,反之。

    展示链表中的数据,就是将链表中所有的数据依次打印输出。链表不像顺序表有“索引”,链表只能从头节点开始依次往下找,直到尾节点。所以链表不能使用 for 循环进行遍历,只能使用 while 循环进行遍历,并使用一个游标 cur 来记录当前所处的节点,通过游标 cur 向链接域指向的节点(下一个节点)移动来遍历,当链接域为空(尾节点)时停止。

    实现 show() 方法时,为了更形象地展示链表中每个节点的关系,我在相邻两个节点之间使用右箭头连接(空链表无效果)。

    if __name__ == '__main__':
        s = SingleLinkList()
        print("is_empty: ", s.is_empty())
        s.show()

    运行结果:

    is_empty:  True
    空链表

    四、实现单向链表中添加数据的功能

        def add(self, data):
            node = Node(data)
            node.next = self.__head
            self.__head = node
    
        def append(self, data):
            if self.is_empty():
                self.add(data)
                return
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            node = Node(data)
            cur.next = node
    
        def length(self):
            length = 0
            cur = self.__head
            while cur is not None:
                length += 1
                cur = cur.next
            return length
    
        def insert(self, index, data):
            if index <= 0:
                self.add(data)
                return
            if index > self.length() - 1:
                self.append(data)
                return
            cur = self.__head
            for i in range(index-1):
                cur = cur.next
            node = Node(data)
            node.next = cur.next
            cur.next = node

    添加数据到单向链表中,可以从头部添加、从尾部添加或从指定位置添加。

    无论将数据添加到链表的哪个位置,都要先创建一个新节点,新节点里存放对应的数据,然后将新节点添加到指定的位置。

    add(data):从头部添加时,链表原来的头节点会成为第二个节点,新节点成为头节点,所以先将新节点的链接域指向原来的头节点,然后将链表的头指向新节点。如果原来的链表为空,则链表的头原来是指向空,所以直接将链表的头指向新节点即可,代码不用变。

    append(data):从尾部添加时,先找到链表的尾节点,然后将尾节点的链接域指向新节点。如果原来的链表为空,则链表没有尾节点,这时候与从头部添加一样,直接调用即可。

    insert(index, data):在指定位置添加数据时,要使用一个游标 cur 来找到此位置的前一个节点,将新节点的链接域指向指定位置原来的节点,然后将游标记录的节点(指定位置的前一个节点)的链接域指向新节点,这样就成功将新节点插入到了指定位置。

    如果指定的位置是负数或超过了链表最大长度,则需要特殊处理,上面的处理是负数在头部添加,超过最大长度在尾部添加。也可以直接抛出 IndexError ,这个可以自己按需选择。

    同时,上面实现了获取单向链表长度的方法 length(),返回链表当前的节点个数。

        s.add(1)
        s.add(10)
        s.append(2)
        s.append(3)
        s.append(4)
        s.show()
        s.insert(1, 20)
        s.show()
        print("链表长度:", s.length())

    运行结果:

    10 → 1 → 2 → 3 → 4
    10 → 20 → 1 → 2 → 3 → 4
    链表长度: 6

    五、实现单向链表的查询和修改功能

        def is_exist(self, value):
            cur = self.__head
            while cur is not None:
                if cur.data == value:
                    return True
                cur = cur.next
            return False
    
        def index(self, value):
            index = 0
            cur = self.__head
            while cur is not None:
                if cur.data == value:
                    return index
                cur = cur.next
                index += 1
            return -1
    
        def setitem(self, index, value):
            if index < 0:
                raise IndexError
            if index > self.length() - 1:
                raise IndexError
            cur = self.__head
            for i in range(index):
                cur = cur.next
            cur.data = value

    is_exist(value):判断一个数据是否存在链表中,遍历单向链表的每个节点,如果节点的数据值与目标值相等,则说明链表中存在目标值。

    index(value):返回一个数据在链表中的第几个节点,与判断是否存在的实现方式一样,这里返回的是数据处于第几个节点中,如果链表中没有这个数据,则返回-1。

    setitem(index, value):修改指定位置的节点的数据,先根据给定的值,找到链表中该位置的节点,然后修改节点中的数据。如果数值小于零或大于链表长度,抛出 IndexError 。

        print(s.is_exist(200))
        print(s.index(20))
        s.setitem(2, 30)
        s.show()

    运行结果:

    False
    1
    10 → 20 → 30 → 2 → 3 → 4

    六、实现单向链表的删除功能

        def remove(self, index):
            if index < 0:
                raise IndexError
            if index > self.length() - 1:
                raise IndexError
            cur = self.__head
            prev = None
            for i in range(index):
                prev = cur
                cur = cur.next
            if cur == self.__head:
                self.__head = self.__head.next
                return
            prev.next = cur.next
    
        def delete(self, value):
            cur = self.__head
            prev = None
            while cur is not None:
                if cur.data == value:
                    if cur == self.__head:
                        self.__head = self.__head.next
                        return
                    prev.next = cur.next
                    return
                prev = cur
                cur = cur.next
    
        def delete_all(self, value):
            cur = self.__head
            prev = None
            while cur is not None:
                if cur.data == value:
                    if cur == self.__head:
                        self.__head = self.__head.next
                        self.delete_all(value)
                    else:
                        prev.next = cur.next
                        self.delete_all(value)
                prev = cur
                cur = cur.next

    remove(index):删除指定位置的节点,通过游标 cur 找到节点,将该节点删除后,要保证链表不断开,就要将该位置的前一个节点的链接域指向该位置的后一个节点,所以再使用一个游标 prev 来记录当前节点的前一个节点。如果删除的是头节点,则直接将链表的头指向第二个节点。如果指定的位置小于零或超过链表长度,则抛出 IndexError 。

    delete(value):删除指定值的节点,先遍历链表,找到对应值的节点,然后将该节点的前一个节点的链接域指向该节点的后一个节点,这里也是使用两个游标来记录节点和前一个节点的位置。如果删除的是头节点,则直接将链表的头指向第二个节点。

    使用这个方法,如果链表中有多个满足条件的节点,只会删除最前面的一个节点。

    delete_all(value):删除数据等于指定值的所有节点,如果链表中有多个节点的数据与目标值相等,删除第一个节点后,链表的长度发生了改变,继续遍历和删除节点,会出现删除不完全甚至程序出错的情况。所以在删除第一个节点之后,递归调用自身,这样重新遍历时使用的是新的链表长度,不会出现漏删或错误。

        s.remove(3)
        s.show()
        s.delete(4)
        s.show()
        s.add(4)
        s.insert(3, 4)
        s.insert(3, 4)
        s.append(4)
        s.append(4)
        s.show()
        s.delete_all(4)
        s.show()

    运行结果:

    10 → 20 → 30 → 3 → 4
    10 → 20 → 30 → 3
    4 → 10 → 20 → 4 → 4 → 30 → 3 → 4 → 4
    10 → 20 → 30 → 3

    以上就是用 Python 实现的单向链表及单向链表的一些简单操作方法。
     

     

    展开全文
  • 1,单向链简洁。...根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转; 3,代码实现。 #include #include <math.h>

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,603
精华内容 32,241
关键字:

单向链表