python之单链表

2021-08-13 14:25:08

前置疑问

Q1 C语言中实现单链表需要用到结构体，python中如何实现?
Q2 面向过程和面向对象实现一个单链表到底有什么不同的感受？

学习内容

1、定义单链表
2、单链表的实现
3、单链表的方法
4、单链表和顺序表的区别

学习时突发疑问

Q3 python中实现链表的时候，为什么要定义两个类Node一个SingleList
Q4 current和current.next 分别代表什么？
Q5 什么时候用current？什么时候用current.next?

学习产出

1、定义单链表

  1. 单链表是线性表，一个单链表是由一个一个节点构成，每个节点有两个域，一个数据域，一个指针域。
  2. “链”表示是一个接着一个，如何实现这种表示，前面一个节点指针域存放后一个节点的地址。谁在谁前面就是前驱，谁在谁后面就是后继，头节点不存在前驱，尾结点不存在后继。

2、单链表的实现

A1

  1. 节点的表示
    用C语言面向过程表示，可以用typedef + struct 来表示一个节点如下：
typedef struct node
{
	ElemType data;
	struct node *next;
}Node, *LinkList;

但是刚学完python如何实现这个节点呢？用类，造一个出来

class Node:
	def __init__(self, data):
	    self.data = data
	    self.next = None
  1. 链表的表示

C语言中用如下方法表示创建好了一个链表L

LinkList L = (LinkList)malloc(sizeof(Node));
L->next = NULL

python之单链表

class SingleList:

    """实现单链表"""
    def __init__(self, node=None):
        self._head = node

my_list = SingleList()

python之单链表
python之单链表
图片由python Tutor生成

A3
为什么要创建两个类呢？因为最终的操作是只用链表这个对象去操作里面的节点，节点是一个对象，需要一个类，链表也是个对象，也需要个类。

3、单链表的常规操作

  1. is_empty
'''判断链表是否为空'''

    def is_empty(self):
        return self._head is None
  1. length
    def length(self):
        current = self._head
        count = 0
        while current is not None:
            count += 1
            current = current.next

        return count
  1. travel
'''遍历链表'''
    def travel(self):
        current = self._head
        while current is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")
  1. add
'''在链表头部插入节点，头插法'''
    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            node.next = self._head
            self._head = node
  1. append
'''在链表尾部插入元素，尾插法'''
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = node

6.insert

'''
        在某个位置插入链表
        两个特殊位置
        1、在0位置 add
        2、在最后一个位置 append
        
        在插入一个节点的时候需要考虑当前位置的前一个节点。
    '''
    def insert(self, item, pos):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            pre = self._head
            count = 0
            while count < (pos - 1):
                pre = pre.next
                count += 1
            node.next = pre.next
            pre.next = node
  1. remove
'''
        删除节点
        需要注意如果删除的节点就是第一个怎么操作？
    '''
    def remove(self, item):
        current = self._head
        if self.is_empty():
            return
        elif current.data == item:
            self._head = current.next
        else:
            previous = None
            while current is not None and current.data != item:
                previous = current
                current = current.next

            previous.next = current.next
  1. search
    '''查找链表中的节点'''
    def search(self, item):
        found = False
        if self.is_empty():
            return found
        else:
            current = self._head
            while current is not None and not found:
                if current.data == item:
                    found = True
                else:
                    current = current.next
        return found

8.实现上面操作

if __name__ == "__main__":
    my_list = SingleList()

    print("add操作：")
    my_list.add(98)
    my_list.add(99)
    my_list.travel()
    print("{:#^50}".format(""))

    print("append操作：")
    my_list.append(100)
    my_list.append(101)
    my_list.append(102)
    my_list.append(103)
    my_list.travel()
    print("{:#^50}".format(""))

    print("insert操作：")
    my_list.insert(99, 0)
    my_list.insert(104, 10)
    my_list.insert(19, 3)
    my_list.insert(56, 5)
    my_list.travel()
    print("{:#^50}".format(""))

    print("remove操作：")
    my_list.remove(19)
    my_list.remove(56)
    my_list.travel()
    print("{:#^50}".format(""))

    print("search操作：")
    print(my_list.search(1000))
    print(my_list.search(101))

    print("链表长为：{0}".format(my_list.length()))

python之单链表

4、链表与顺序表的区别

操作 链表时间 顺序表时间
表头插入元素add O(1) O(n)
表尾插入元素append O(n) O(1)
在任意位置插入元素insert O(n) O(n)
访问元素 O(n) O(1)

5、关于current和current.next的区别

A4 和 A5
current指的是当前整个节点，而current.next指的是下一个节点的地址
python之单链表
图片由python Tutor生成

用两个函数来测试分别用current和current.next做while循环终止条件，count遍历了多少次，我猜测是用current 比 current.next 的count要多一次。

    def traverse_next(self):
        current = self._head
        count = 0;
        if self.is_empty():
            return count
        else:
            while current.next is not None:
                count += 1
                current = current.next
        return count

    def traverse(self):
        current = self._head
        count = 0
        if self.is_empty():
            return count
        else:
            while current is not None:
                count += 1
                current = current.next
        return count

python之单链表
和我的猜测一样，current—>7 ， current.next —> 6

将上述代码修改为如下，加上一个返回current.data。会发生什么？

    def traverse_next(self):
        current = self._head
        count = 0;
        if self.is_empty():
            return count
        else:
            while current.next is not None:
                count += 1
                current = current.next
        return count,current.data

    def traverse(self):
        current = self._head
        count = 0
        if self.is_empty():
            return count
        else:
            while current is not None:
                count += 1
                current = current.next
        return count, current.data

python之单链表
代码结果表明：虽然current和current.next 都能当遍历的条件，但是current.next可以返回尾结点的数值域，而current将一整个节点遍历完，最后current = None了，当调用current.data自然会报错。

用append()在表尾增加元素和遍历单链表说明什么时候用current和什么时候用current.next

 '''在链表尾部插入元素，尾插法'''
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = node

    def append2(self,item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            previous = None
            while current is not None:
                previous = current
                current = current.next
            previous.next = node

	'''遍历单链表'''
    def travel(self):
        current = self._head
        while current is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")
        
    def travel2(self):
        current = self._head
        while current.next is not None:
            print("{0}".format(current.data), end=" ")
            current = current.next
        print(" ")

if __name__ == "__main__":
    my_list = SingleList()

    my_list.append(100)
    my_list.append(101)
    my_list.append(102)
    my_list.append(103)
    my_list.append2(104)

    print("用current当循环的条件：")
    my_list.travel()
    print("{:#^50}".format(""))
    print("用current.next当循环的条件：")
    my_list.travel2()
    print(my_list.length())

python之单链表
在向表尾添加元素的时候用current.next方便，遍历链表用current，用current.next会少表尾最后一个元素。

A2
由面向过程的C语言和面向对象的python去实现一个链表的感受：

  1. 代码变少了，简洁的背后是需要对面向对像的熟悉，python万物皆对象，每个对象都有三要素 id type value 变量存的是地址。比如C中第一个节点是 current = L->next，python中是 current = self._head
  2. C语言一步一步实现也不能忘记，更容易去思考底层的原理，反而面向对象高级语言，操作简单，但感觉让人变笨了的感觉。
上一篇：MySQL压测工具--sysbench


下一篇：Luogu P6187 [NOI Online 提高组]最小环