用python实现线性链表

线性链表概览

单节点链表

头指针和尾指针为同一节点，尾指针中的指针域为空(None)

一般链表

尾指针中的指针域为空(None)

链表基本数据结构

链表基本单元：节点(Node)

创建Node类

• 值域
• 指针域

class Node:
    """
    the basic element of a linked list
    """
    def __init__(self, val, pnext):
        self.value = val
        self.pnext = pnext

链表类

创建LinkedList类

• head: 头指针
• tail: 尾指针
• length: 链表长度

class LinkedList:
    """
    a linked list object
    """
    def __init__(self):
        self.head = None
        self.tail = self.head
        self.length = 0

链表操作函数

self参数为对象本身，类似于C++中的this指针

向链表中插入节点

创建insert_value函数

• val: 节点值域
• loc: 节点位置，默认为None

def insert_value(self, val, loc=None):
    """
    insert node to the list
    :param val: insert value
    :param loc: insert with index
    :return:
    """
    if self.list_empty():
        # if the list is empty
        self.head = Node(val, None)
        self.tail = self.head
        self.length = 1
    else:
        if (not loc) | (loc == self.length):
            # if insert element without location or at the tail
            new_node = Node(val, None)
            self.tail.pnext = new_node
            self.tail = new_node
            self.length += 1
        else:
            new_node = Node(val, None)
            last_node = self.head
            for index in range(self.length):
                if index == (loc - 1) - 1:
                    break
                else:
                    last_node = last_node.pnext
            next_node = last_node.pnext
            last_node.pnext = new_node
            new_node.pnext = next_node
            self.length += 1

删除链表中的节点

创建delete_value函数

• loc: 删除的节点位置

def delete_value(self, loc=None):
    """
    delete value from list
    :param loc: the location of list
    :return:
    """
    if not self.list_empty():
        if loc:
            last_node = self.head
            for index in range(self.length):
                if index == (loc - 1) - 1:
                    break
                else:
                    last_node = last_node.pnext
            next_node = last_node.pnext.pnext
            last_node.pnext = next_node
        else:
            now_node = self.head
            while now_node:
                if now_node.pnext.pnext is None:
                    now_node.pnext = None
                    break
                else:
                    now_node = now_node.pnext
        self.length -= 1

判断链表是否为空

def list_empty(self):
    """
    if the list is empty
    :return:
    """
    if self.head is None:
        return True
    else:
        return False

打印链表内容

def list_traverse(self):
    """
    visit all elements of the list
    :return:
    """
    if not self.list_empty():
        now_node = self.head
        print('-'*15)
        while now_node:
            print("value: ", now_node.value)
            now_node = now_node.pnext

测试案例

创建程序入口

if __name__ == "__main__":
    my_linkedlist = LinkedList()
    for i in range(5):
        my_linkedlist.insert_value(i)
    my_linkedlist.list_traverse()
    my_linkedlist.insert_value(['this', 'is', 'a', 'list'], 3)
    my_linkedlist.list_traverse()
    my_linkedlist.delete_value(2)
    my_linkedlist.list_traverse()

运行结果如下

---------------
value:  0
value:  1
value:  2
value:  3
value:  4
---------------
value:  0
value:  1
value:  ['this', 'is', 'a', 'list']
value:  2
value:  3
value:  4
---------------
value:  0
value:  ['this', 'is', 'a', 'list']
value:  2
value:  3
value:  4

源码

点击此处访问