数据结构必会｜链表的思想和实现（Python）

链表

1. 链表的概念

​ 链表的结构就像平时生活中所见到的锁链一样，是一种一环套着一环的结构。在数据结构的链表中，每一环都由“数据域”和“指针域”两部分构成。具体结构如下图所示：

​ 如图所示就是链表的结构，数据域用户存储当前结点的元素信息，指针域用于链接下一个结点，需要注意的是链表是无序的，也就是说我们只需要维持元素之间的相对位置，并不需要在连续的内存空间中维护这些位置信息。

2. 链表的创建

​ 链表的创建和它的原理一样，我们需要对每个结点进行初始化，结点中包含着数据域data和指针域next，有了结点之后还需要制定结点的指向函数使得结点之间能够链接起来，具体的实现方法如下：

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

    # 获取节点的值
    def getData(self):
        return self.data

    # 获取下一个节点地址
    def getNext(self):
        return self.next

    # 设置节点的值
    def setData(self, newData):
        self.data = newData

    # 设置节点指向
    def setNext(self, newnext):
        self.next = newnext

​ 测试结果如下：

# 设置结点的数据域
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)

# 设置结点指针指向的位置
temp1.next = temp2
temp2.next = temp3
temp1.setNext(temp3)

# 获取结点的值
temp2.getNext().getData()

# 输出
95

3. 链表功能的实现

​ 对于链表来说，除了创建链表之外，我们还需要创建一个类来实现链表的功能。

• printlink：实现链表的打印；
• length：实现链表长度的计算；
• search：实现链表中元素的查找；
• remove：实现链表中元素的移除。

​ 具体的实现方式如下：

class UnorderedList:
    # 没有元素构建一个空列表
    def __init__(self):
        self.head = None

    # 判断列表是否为空
    def isEmpty(self):
        return self.head == None

    # 添加节点
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    # 遍历链表
    def printlink(self):
        if self.head == None:
            print("该链表为空链表！")
        p = self.head
        while p != None:
            print(p.getData(), end="->")
            p = p.getNext()

    # 链表的长度
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    # 查找元素
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    # 移除元素
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

​ 测试结果如下：

# 设置结点的数据域
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)

# 设置结点指针指向的位置
linklist = UnorderedList()
linklist.head = temp1
temp1.next = temp2
temp2.next = temp3

# 使用功能类中的add进行元素的添加
linklist.add(9)
# 打印链表长度
print(linklist.length())

# 输出
4

​ 使用循环构造链表：

link_list = UnorderedList()
for i in range(5):
    link_list.add(i)
node = link_list.head
node.getData()

# 输出
4