Python实现链表

作者: Yznx_请叫我小哥 | 来源:发表于2019-08-25 10:22 被阅读0次

用Python玩转数据结构

链表

节点类

根据在前学过的数据结构，那么必须有节点，Python里面没有指针的说法，所以我们用引用来实现

节点类的方法

节点类最基本的功能包括：更新数据，查询数据，更新后继节点和查询后继节点。

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

    def get_data(self):
        """
        获取当前节点的数据
        :return: 返回当前节点的数据
        """
        return self.data

    def set_data(self, data):
        """
        设置节点的数据为传入的数据
        :param data:
        :return: 无返回
        """
        self.data = data

    def get_next(self):
        """
        获取当前节带点的指向
        :return: 返回指向的对象
        """
        return self.next

    def set_next(self, next_node):
        """
        修改节点的指向
        :param next_node:
        :return:无返回
        """
        self.next_node = next_node

链表类

我们把节点类先实现，然后再来实现链表类。我们定义一个链表类，并实现初始化方法。在初始化方法中定义了两个属性，分别是head 和length属性。head属性表明头节点，在初始化的时候指向None。length属性表明链表的长度，方便判断列表是否为空和返回链表的长度。

class Linked_list(object):
    def __init__(self):
        """
        初始化方法，定义一个长度属性方便统计和判断
        """
        self.head = None
        self.length = 0

链表类的方法

然后我们一个想想我们的链表类需要哪些方法，这是有链表的特性觉得的不是吗？大概列一个列表吧：

在末尾插入数据
在开头插入数据
在指定位置插入数据
修改指定位置的数据
获取指定位置的数据
查找数据在链表中的数据
删除指定位置的数据
展示整个链表
删除整个链表
判断这个链表是否为空

大概就是这些看起来是不是有点多，但是不用担心，我们一点一点的来实现。

判断链表是否为空

首先是判断一个链表是否为空，这个很好实现，我们先看代码：

    def isEmpty(self):
        """
        判断链表是否为空，如果为空返回True，否则为False
        :return:
        """
        return self.length == 0

除去注释也就一行代码的事情，用链表的长度和0做一个比较，不相等返回False相等返回True然后就能很好的判断了。

获取链表的长度

同样的获取链表的长度也很简单：

    def get_length(self):
        return self.length

在链表末尾插入数据

然后就是在末尾插入数据：

    def append(self, data_or_node):
        """
        在链表的末尾增加一个节点
        :param data_or_node:
        :return:
        """
        item = None
        # 这一个判断是为了判断传进来的数据是什么类型的
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if not self.head:
            self.head = item
            self.length += 1
        else:
            node = self.head
            while node.next_node:
                node = node.next_node
            node.next_node = item
            self.length += 1

首先是判断传入进来的数据是什么类型，如果已经是一个节点类的话我们就不用转换，如果不是，我们就将其转换为节点类。这里用到了isinstance()方法，这个方法的作用是判一个对象是否是一个已知的类型，考虑继承的情况。然后判断这个链表的头结点是否存在，也可以通过判断链表的长度来实现。如果头节点不存在，就将这个节点变为头节点。所以有了这个引用，将item的值赋值给head。如果不是的话我们首先就要找到尾节点，通过头节点开始循环，一直找到尾节点，然后引用。不管是那种情况都不能忘记将链表的长度加上1

在链表的头部插入数据

在头部插入数据也很简单，

    def add(self, data_or_node):
        """
        在链表的最前方插入一个数据
        :param data_or_node:
        :return:
        """
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if not self.head:
            self.head = item
            self.length += 1
        else:
            next_node = self.head
            self.head = item
            item.next_node = next_node
            self.length += 1

大部分都差不多，只是在判断不是空链表之后的处理有点不一样。我们将之前头节点的值赋值给一个变量，然后将我们传入的变量指向给原头节点，同时将头节点指向我们传入的变量。

在指定位置插入节点

我们可以通过指定位置插入节点这个是很必要的一个方法，先看代码：

    def insert(self, index, data_or_node):
        """
        根据给定的索引在链表中插入一个节点
        :param index: 索引
        :param data_or_node: 数据
        :return: 无返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return
        item = None
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if index == 0:
            self.add(item)
            return

        j = 0
        node = self.head
        prev = self.head
        while j < index:
            prev = node
            node = node.next_node
            j += 1
        prev.next_node = item
        item.next_node = node
        self.length += 1

对于所有给出索引的方法来说，我们都需要判断这个链表是否为空和给定的索引是否越界。然后再把传入的节点通过判断转换为节点类。如果索引的值是0的话就是在头部插入，我们直接调用在前面定义的内部方法就好，然后记得return结束函数，不然那你会将你的所有的节点的值都改变。然后就是关键的步骤，我们定义三个变量，作用分别是：计数器、记录前置节点和记录当前节点。最开始的节点都为头节点，然后开始循环，当j小于索引值的时候呢，循环，同时将node的值赋值给prev，将节点记录下来。当找到插入节点的位置的时候，我们将prev指向我们传入的节点，然后将传入的节点再指向给item就完成在指定位置插入。只要是涉及到节点个数的变化的操作的时候一定要记得对length进行对应的操作。

删除指定位置的节点

说完了增加，按照惯例就是删除了。首先是删除指定位置的节点：

    def delete(self, index):
        """
        根据给定的索引删除一个节点
        :param index: 索引
        :return: 无返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        if index == 0:
            self.head = self.head.next_node
            self.length -= 1

        j = 0
        node = self.head
        prev = self.head
        while j < index:
            prev = node
            node = node.next_node
            j += 1
        prev.next_node = node.next_node
        self.length -= 1

首先还是几个判断，然后如果是删除头节点，我们将头节点的值指向头节点的下一个。如果不是，就和插入很像了，找到索引对应的位置，然后将prev直接指向node的下一个，然后链表长度减1。

删除整个链表

删除了一个节点就像删除整个链表，这个代码也超级简单：

    def clear(self):
        """
        清除链表
        :return: 无返回
        """
        self.head = None
        self.length = 0

我们只需要将链表的头节点再指向为空，然后长度变为0就好。

修改指定位置的节点的值

删除也很简单，下面来说修改，修改指定位置节点的值：

    def updata_node_item(self, index, data):
        """
        根据给出的索引更新一个节点的值
        :param index: 索引
        :param data: 更新的值
        :return: 无返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        j = 0
        node = self.head
        while j < index:
            node = node.next_node
            j += 1
        node.data = data

就只是常规的判断然后是循环找到节点后修改值就好。

根据索引获得对应节点的值

查找是一个很重要的功能，有两种需要我们实现，先来第一种：根据索引查找对应的值：

 def get_node_item(self, index):
        """
        根据索引获取获取节点的值
        :param index: 索引
        :return: 返回索引对应节点的值
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        j = 0
        node = self.head
        while j < index:
            node = node.next_node
            j += 1
        return node.data

和修改很类似，不同的是我们直接返回值就好

根据值查对应的节点的索引

我们也可以传一个值然后找对应的索引，这样就能做到：

    def get_node_index(self, data):
        """
        查找一个数据的索引
        :param data:数据
        :return:索引
        """
        node = self.head
        j = 0
        while node.next_node:
            if node.data == data:
                return j
            else:
                node = node.next_node
            j += 1
        if j == self.length:
            print("%s is not found " % str(data))

其实都差不多，但是呢有一种情况需要注意，就是如果当j的值都等于链表的长度的时候说明，链表当中没有这个值。

展示链表

其实到这里就差不多了，然后就是一个展示整个链表的方法：

    def show(self):
        """
        展示链表
        :return:
        """
        if self.isEmpty():
            print("this is a empty linked list")
        n = 0
        node = self.head
        while n < self.length:
            print("node %d : %s" % (n, node.data))
            node = node.next_node
            n += 1

试试效果

mylinked = Linked_list()
for i in range(10):
    mylinked.append(i)
mylinked.show()
print(mylinked.get_length())
print(mylinked.get_node_index(4))
print(mylinked.get_node_item(5))
print(mylinked.updata_node_item(4, 20))
print(mylinked.delete(8))
print(mylinked.insert(0, 420))
mylinked.show()

结果：

node 0 : 0
node 1 : 1
node 2 : 2
node 3 : 3
node 4 : 4
node 5 : 5
node 6 : 6
node 7 : 7
node 8 : 8
node 9 : 9
10
4
5
None
None
None
node 0 : 420
node 1 : 0
node 2 : 1
node 3 : 2
node 4 : 3
node 5 : 20
node 6 : 5
node 7 : 6
node 8 : 7
node 9 : 9

Process finished with exit code 0

完整代码传送门：点这里