单向链表

链表

简介

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢，使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

结构

image-20210309225425257

代码

需求

  1. 验证列表是否有值
  2. 从头部插入元素
  3. 从尾部插入元素
  4. 指定位置插入元素
  5. 删除元素
  6. 验证节点是否在链表中
  7. 根据节点索引查找值
  8. 链表排序
  9. 修改数据

代码实现

# !/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2021/3/8 下午8:47
# @Author : SR
# @Email : srcoder@163.com
# @File : link_list.py
# @Software: PyCharm

# 基础配置
class Node:
 	'''节点'''
    def __init__(self, data):
        self.data = data  # 存储数据
        self.next = None  # 下一个节点


class SingleLinkList:
    '''链表'''
    def __init__(self):
        self.header = None  # 节点头部
        self.length = 0  # 链表长度

验证列表是否有值

 def is_empty(self):
        '''判断是否为空'''
        if not self.length == 0:	#　链表长度为0则没有值
            return False
        return True

image-20210310092027334

头插法

    def create_linklist_by_head(self, node):
        '''头插法'''
        if self.is_empty():
            self.header = node
        else:

            node.next = self.header
            self.header = node

        self.length += 1

image-20210310092136288

尾插法

  def create_linklist_by_tail(self, node):

        '''尾插法'''

        current_node = self.header
        if self.is_empty():
            self.create_linklist_by_head(node)
		else:
            while not current_node.next == None:
                current_node = current_node.next  #　获取最后一个元素  
            current_node.next = node	#　最后一个元素下一个元素即为新增节点
        self.length += 1

image-20210310092909591

指定元素加入元素

 def create_linklist_by_insert(self, node, index):
        '''插入在指定位置'''
        current_node = self.header  # 获取首节点

        if index <= 0 or self.length == 0:
            index = 1
       
        if index == 1:	#　索引为1的时候　默认直接插入到首位
            self.create_linklist_by_head(node)
        elif index == 2:
            node.next = self.header.next

            current_node.next = node

            self.length += 1
        elif index > self.length:	#　索引大于链表长度　默认插入到尾部
            self.create_linklist_by_tail(node)
           
        else:
            for i in range(1, index - 1):
                current_node = current_node.next  # 获取插入之前的元素 例如想插在3号位置　此时节点为2号元素
            node.next = current_node.next  # 将插入的元素与后一位联系起来　例如此时插入3号位置　

            current_node.next = node

            self.length += 1

插入首号位置

image-20210310211410992

插入大于链表长度位置

image-20210310211707810

插入2号位置

image-20210310211949503

插入小于0号位置

image-20210310212243796

在首位与末位之间任意插入

image-20210310212448109

删除指定元素

 def delete_linklist_by_index(self, index):
        if self.is_empty():
            print('当前链表无数据')
        else:
            if index not in range(1, self.length):

                while index not in range(1, self.length):
                    print("死扑街啊　不知道从哪里删除吗　重新输入啊!")
                    index = eval(input("请重新输入啊>>:"))
            if index == 1:
                self.header = self.header.next
            elif index == 2:
                current_node = self.header
                current_node.next = current_node.next.next
            else:
                current_node = self.header
                for i in range(1, index - 1):
                    current_node = current_node.next
                current_node.next = current_node.next.next
        	self.length -= 1

删除首位元素

image-20210310220851595

删除末位元素

image-20210310221054756

删除2号元素

image-20210310222521366

删除首位到末尾之间任意元素

image-20210310222727483

验证值是否存在链表中

 def isContainNum(self, number):
        flag = False
        current_node = self.header

        for i in range(1, self.length):
            if current_node.data == number:
                print("该链表包含%s--->位于%s位置" % (number, i))

                flag = True
                break	#　找到元素则直接退出循环
             current_node = current_node.next
        if not flag:
            print("该值%s不在链表之中" % number)

image-20210311092253284

根据索引取值

    def searchNodeByIndex(self, index):
        current_node = self.header
        if self.is_empty():
            print("当前链表为空")
        else:
            if index not in range(1, self.length):
                while index not in range(1, self.length):
                    print('死扑街啊　索引有误　请重新输入啊')
                    index = eval(input('请重新输入啊>>:'))
            for i in range(1, index):
                current_node = current_node.next

            return current_node

根据索引修改链表值

   def alterNumByIndex(self, index, number):
        if self.is_empty():
            print("当前链表为空　无可修改的数据!")
        else:
            current_node = self.header
            if index not in range(1, self.length):
                while index not in range(1, self.length):
                    print("死扑街啊 索引写错了")
                    index = eval(input("请重新输入啊>>:"))
                for i in range(1, index):
                    current_node = current_node.next
                current_node.data = number

image-20210311101341032

遍历链表

    def travel(self):
        current_node = self.header

        if self.length == 0:
            print("当前链表为空")
        else:
            for i in range(self.length):
                print("%s " % current_node.data, end=" ")

                current_node = current_node.next
            print("
")

链表排序

    def list_sort(self):
        for i in range(self.length):
            current_node = self.header
            for j in range(self.length - 1 - i):
                if current_node.data > current_node.next.data:
                    temp = current_node.data
                    current_node.data = current_node.next.data
                    current_node.next.data = temp
                current_node = current_node.next

完整代码

# !/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2021/3/10 上午9:04
# @Author : SR
# @Email : srcoder@163.com
# @File : link_list.py
# @Software: PyCharm

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class SingleLinkList:
    def __init__(self):
        self.header = None

        self.length = 0  # 链表长度

    def is_empty(self):
        '''判断是否为空'''
        if not self.length == 0:
            return False
        return True

    def create_linklist_by_head(self, node):
        '''头插法'''
        if self.is_empty():
            self.header = node
        else:

            node.next = self.header
            self.header = node

        self.length += 1

    def create_linklist_by_tail(self, node):

        '''尾插法'''

        current_node = self.header
        if self.is_empty():
            self.create_linklist_by_head(node)
        else:

            while not current_node.next == None:
                current_node = current_node.next
            current_node.next = node
        self.length += 1

    def create_linklist_by_insert(self, node, index):
        '''插入在指定位置'''
        current_node = self.header  # 获取首节点

        if index <= 0 or self.length == 0:
            index = 1

        if index == 1:
            self.create_linklist_by_head(node)
        elif index == 2:
            node.next = self.header.next

            current_node.next = node

            self.length += 1
        elif index > self.length:
            self.create_linklist_by_tail(node)
        else:
            for i in range(1, index - 1):
                current_node = current_node.next  # 获取插入之前的元素 例如想插在3号位置　此时节点为2号元素
            node.next = current_node.next  # 将插入的元素与后一位联系起来　例如此时插入3号位置　

            current_node.next = node

            self.length += 1

    def delete_linklist_by_index(self, index):
        '''通过索引删除'''
        if self.is_empty():
            print('当前链表无数据')
        else:
            if index not in (1, self.length):

                while index not in (1, self.length):
                    print("死扑街啊　不知道从哪里删除吗　重新输入啊!")
                    index = eval(input("请重新输入啊>>:"))
            if index == 1:
                self.header = self.header.next
            elif index == 2:
                current_node = self.header
                current_node.next = current_node.next.next
            else:
                current_node = self.header
                for i in range(1, index - 1):
                    current_node = current_node.next
                current_node.next = current_node.next.next
        self.length -= 1

    def isContainNum(self, number):
        '''验证链表是否包含某值'''
        flag = False
        current_node = self.header

        for i in range(1, self.length):
            if current_node.data == number:
                print("该链表包含%s--->位于索引%s" % (number, i))

                flag = True
        if not flag:
            print("该值%s不在链表之中" % number)

    def searchNodeByIndex(self, index):
        '''通过索引寻找某节点'''
        current_node = self.header
        if self.is_empty():
            print("当前链表为空")
        else:
            if index not in range(1, self.length):
                while index not in range(1, self.length):
                    print('死扑街啊　索引有误　请重新输入啊')
                    index = eval(input('请重新输入啊>>:'))
            for i in range(1, index):
                current_node = current_node.next

            return current_node

    def alterNumByIndex(self, index, number):
        '''索引修改值'''
        if self.is_empty():
            print("当前链表为空　无可修改的数据!")
        else:
            current_node = self.header
            if index not in range(1, self.length):
                while index not in range(1, self.length):
                    print("死扑街啊 索引写错了")
                    index = eval(input("请重新输入啊>>:"))
                for i in range(1, index):
                    current_node = current_node.next
                current_node.data = number

    def travel(self):
        '''便利链表'''
        current_node = self.header

        if self.length == 0:
            print("当前链表为空")
        else:
            for i in range(self.length):
                print("%s " % current_node.data, end=" ")

                current_node = current_node.next
            print("
")

    def list_sort(self):
        '''链表排序'''
        for i in range(self.length):
            current_node = self.header
            for j in range(self.length - 1 - i):
                if current_node.data > current_node.next.data:
                    temp = current_node.data
                    current_node.data = current_node.next.data
                    current_node.next.data = temp
                current_node = current_node.next


def main():
    # 创建一个单链表对象
    single_link_list = SingleLinkList()  # 实例化

    print('''
              **********************************************************************************************************************
              **********************************************请选择相应的序号完成相应的操作********************************************
              **********************************************************************************************************************
              **         0、结束所有操作！！！！！！                                                                               ***
              **         1、验证链表里面有没有值！                                                                                 ***
              **         2、从头部插入数值！                                                                                       ***
              **         3、从尾部插入数值！                                                                                       ***
              **         4、按指定位置插入数值！                                                                                   ***
              **         5、删除操作！                                                                                            ***
              **         6、查找一个节点是否在链表中！                                                                             ***
              **         7、按下标查找节点处的数值！                                                                               ***
              **         8、给链表排序！                                                                                          ***
              **         9、修改！                                                                                                ***
              **********************************************************************************************************************
              ''')

    while True:
        number = eval(input('请输入上述数字对应的编号>>:').strip())

        if number not in range(1, 9):
            while number not in range(1, 9):
                print("死扑街啊　不认识上面字吗　选择的功能为开发啊!")
                number = eval(input('请重新输入上述数字对应的编号>>:').strip())

        if number == 0:
            return
        elif number == 1:
            print("正在验证链表里面有没有值：")

            if not single_link_list.is_empty():
                single_link_list.travel()
            else:
                print("当前链表无数据!")
            print("
")
        elif number == 2:
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在从头部插入数值：")

            node = Node(int(input("请输入需要插入的值>>:")))

            single_link_list.create_linklist_by_head(node)

            print("操作后链表的状态。")
            single_link_list.travel()

        elif number == 3:

            print("目前的链表状态。")
            single_link_list.travel()

            node = Node(int(input("请输入需要插入的值>>:")))

            if not single_link_list.is_empty():
                print("正在从尾部插入数值：")

                single_link_list.create_linklist_by_tail(node)

                print("操作后链表的状态。")
                single_link_list.travel()
            else:
                single_link_list.create_linklist_by_head(node)

            print("操作后链表的状态。")
            single_link_list.travel()

        elif number == 4:
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在从指定位置插入数值：")

            node = Node(int(input("请输入需要插入的值>>:")))

            index = int(input("请输入需要插入的位置>>:"))

            single_link_list.create_linklist_by_insert(node, index)

            print("操作后链表的状态。")
            single_link_list.travel()

        elif number == 5:
            if not single_link_list.is_empty():
                print("目前的链表状态。")
                single_link_list.travel()

                print("正在从指定位置删除数值：")
                index = int(input("请输入需要删除的位置>>:"))
                single_link_list.delete_linklist_by_index(index)
                print("操作后链表的状态。")
                single_link_list.travel()
            else:
                print("当前链表为空　请添加数据!")
        elif number == 6:
            if not single_link_list.is_empty():
                print("目前的链表状态。")
                single_link_list.travel()
                print("正在查找一个节点是否在链表中:")
                num = eval(input("请输入需要查询的元素>>:"))
                single_link_list.isContainNum(num)
            else:
                print("当前链表为空")
        elif number == 7:

            if not single_link_list.is_empty():
                print("正在按下标查找节点处的数值>>：")
                node = single_link_list.searchNodeByIndex(
                    eval(input("输入下标值>>：")))  # 查找某节点处的值
                print("这个位置的值为：%s" % node.data)
            else:
                print("当前链表为空")
        elif number == 8:
            if not single_link_list.is_empty():
                print("目前的链表状态。")
                single_link_list.travel()
                print("正在排序：")
                single_link_list.list_sort()
                print("操作后链表的状态。")
                single_link_list.travel()
            else:
                print("当前链表为空")

        else:
            if not single_link_list.is_empty():
                print("目前的链表状态。")
                single_link_list.travel()
                print("正在修改（这是在上面排序后的前提下修改。）：")
                index = eval(input("输入要修改的得位置>>："))  # 修改的下角标
                num = eval(input("输入要修改为的数>>："))  # 要修改成的那个数
                single_link_list.alterNumByIndex(index, num)
                print("操作后链表的状态。")
                single_link_list.travel()  # 遍历一遍
            else:
                print("当前链表为空")


if __name__ == '__main__':
    main()
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SR-Program/p/14516620.html