链表结构

以你之姓@ 2023-02-13 05:47 44阅读 0赞

转载自：https://blog.csdn.net/qq\_39422642/article/details/78988976，一篇不错的关于链表的讲解，和大家共享。

1.基础 知识  
1.1 链表的基本结构

链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。   
如图：   
 ![SouthEast][]  
链表的基本元素有：

节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。  
head:head节点永远指向第一个节点  
tail: tail永远指向最后一个节点  
None:链表中最后一个节点的指针域为None值  
但链表也分为单向链表和单向循环链表，双向链表和双向循环链表，如图为单向链表和单向循环链表：

![è¿éåå¾çæè¿°][SouthEast 1]  
写个基本程序测试一下：

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)

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

将list拆分成两个部分，head:第一个元素，tail:其余元素  
向后打印  
打印第一个元素

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)

2.链表的基本操作  
在链表的基本操作中，包括插入，删除等，但要注意的是一下的操作是针对非循环链表的，从头节点开始操作，而且我们不能插入 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

[SouthEast]: https://img-blog.csdn.net/20180106141543707?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzk0MjI2NDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20180106142315947?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzk0MjI2NDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast