python数据结构之链表(linked

2023-01-31 01:01:56 python 数据结构 链表

目录

  1. 基础 知识
    1.1 链表的基本结构
    1.2 节点类和链表节点的定义
    1.3 顺序打印和逆序打印
  2. 链表的基本操作
    2.1 计算链表长度
    2.2 从前,后插入数据
    2.3 查找与删除

参考

1.基础 知识

1.1 链表的基本结构

链表是通过一个个节点组成的,每个节点都包含了称为carGo的基本单元,它也是一种递归数据结构。它能保持数据之间的逻辑顺序,但存储空间不必按照顺序存储。
如图:
这里写图片描述
链表的基本元素有:

  • 节点:每个节点有两个部分,左边部分称为值域,用来存放用户数据;右边部分称为指针域,用来存放指向下一个元素的指针。
  • head:head节点永远指向第一个节点
  • tail: tail永远指向最后一个节点
  • None:链表中最后一个节点的指针域为None值

但链表也分为单向链表和单向循环链表,双向链表和双向循环链表,如图为单向链表和单向循环链表:
这里写图片描述

写个基本程序测试一下:

1.2 节点类和链表节点的定义

节点类定义如下:

class node:
    def __init__(self,cargo = None, next = None):
        self.cargo = cargo
        self.next = next
    def __str__(self):
        #测试基本功能,输出字符串
        return str(self.cargo)
print Node("text")
#输出text

因为任何值都能通过str函数,且能存储下来。

链表怎么定义呢?
我们可以先定义一个一个节点,如下:

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

然后再把每个节点的关系表示出来,就OK了

node1.next = node2
node2.next = node3

1.3 顺序打印和逆序打印

因为先前已经建立了关系,所以可以通过输入第一个节点,循环整个链表然后顺序打印整个链表。

def printList(node):
    while node:
        print node
        node = node.next
printList(node1)
1
2
3

使用递归的方法来打印,主要步骤如下:

  1. 将list拆分成两个部分,head:第一个元素,tail:其余元素
  2. 向后打印
  3. 打印第一个元素
def printBackward(lists):
    if lists == None:
        return
    head = lists
    tail= lists.next
    print head,tail
    printBackward(tail)
    print head,tail
printBackward(node1)
1 2
2 3
3 None
3 None
2 3
1 2

事实上,还能更简便。

def printBackward(lists):
    if lists == None:return
    printBackward(lists.next)
    print lists
printBackward(node1)

在链表的基本操作中,包括插入,删除等,但要注意的是一下的操作是针对非循环链表的,从头节点开始操作,而且我们不能插入 None值到链表中。

2.1 计算链表长度

class Node(object):
#节点类
    #功能:输入一个值data,将值变为一个节点
    def __init__(self, data, next = None):
        self.data = data
        self.next = next

    def __str__(self):
        return self.data

class LinkedList(object):

    def __init__(self, head = None):
        self.head = head
    def __len__(self):
        #功能:输入头节点,返回链表长度
        curr = self.head
        counter = 0
        while curr is not None:
            counter += 1
            curr = curr.next
        return counter

2.2 从前,后插入

从前插入:

  • 被插入数据为空,返回
  • 使用该输入数据创建一个节点,并将该节点指向原来头节点
  • 设置该节点为头节点

时间复杂度和空间复杂度均为O(1)

    def insertToFront(self,data):
        #功能:输入data,插入到头节点前,并更改为头节点
        #输出:当前头节点
        if data is None:
            return None
        node = Node(data,self.head)
        self.head = node
        return node

从后:append

  • 若输入数据为空,返回None
  • 若头节点为空,直接将输入数据作为头节点
  • 遍历整个链表,直到当前节点的下一个节点为None时,将当前节点的下一个节点设置为输入数据

时间复杂度为O(n),空间O(1)

    def append(self,data):
        #功能:输入data,作为节点插入到末尾
        if data is None:
            return None
        node = Node(data)
        if self.head is None:
            self.head = node
            return node
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = node
        return node

2.3 查找与删除

查找

  • 若查找的数据为空,返回
  • 设置头节点为当前节点,若当前节点不为None,遍历整个链表
  • 若当前节点的data与输入的data相同,但会当前节点,否则轮到下一个节点

可见时间复杂度为O(n),空间复杂度为O(1).

    def find(self,data):
        #功能:查找链表的节点data与data相同的节点
        if data is None:
            return None
        curr_node = self.head
        while curr_node is not None:
            if curr_node.data == data:
                return curr_node
            curr_node = curr_node.next
        return None

删除1
申请两个变量,如果遇到匹配的,不用删除,直接将匹配节点的前一节点指向匹配节点的下一节点,因此需要定义一个前节点和一个当前节点,当前节点用来判断是否与输入数据匹配,前节点用来更改链表的指向。

  • 若输入数据为None,返回
  • 将头节点设置为前节点,头节点的下一个节点设置为当前节点
  • 判断前节点是否与输入数据匹配,若匹配,将头节点设置为当前节点
  • 遍历整个链表,若当前节点与输入数据匹配,将前节点的指针指向当前节点的下一个节点,否则,移到下一个节点

时间复杂度为O(n),空间复杂度为O(1).

   def delete(slef,data):
        #删除节点
        if data is None:
            return None
        if self.head is None:
            return None
        if self.head.data == data:
            self.head = self.head.next
            return
        prev_node = self.head
        curr_node = self.head.next
        while curr_node is not None:
            if curr_node.data == data:
                prev_node.next = curr_node.next
            else:
                prev_node = curr_node
                curr_node = curr_node.next

删除2
第二种解决办法就是只定义一个变量作为当前节点,使用它的下一个节点去判断是否与数据数据匹配,若匹配,直接将当前节点指向下下一个节点。

时间复杂度为O(n),空间复杂度为O(1).

    def deleteAlt(self):
        #只定义一个变量来完成删除操作
        if data is None:
            return 
        if self.head is None:
            return 
        if self.head.data == data:
            self.head = self.head.next
            return
        curr_node = self.head
        while curr_node.next is not None:
            if curr_node.next.data == data:
                curr_node.next = curr_node.next.next
                return
            curr_node = curr_node.next

reference

Linked lists¶
python实现的数据结构与算法:链表
Python数据结构-链表
Solution Notebook

相关文章