[Python]数据结构–链表

‘Festinatione facit vastum’

• 链表的概念
• 单链表的实现
• 循环单链表的实现

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相比于线性表顺序结构，操作复杂。

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

代码实现

# -*- coding: utf-8 -*-

"""
@IDE: PyCharm
@FileName: linked list
@Author: JYFelt
@date： 201801111649 
@这里写描述：
"""
__author__ = 'JYFelt'


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


class Linklist():
    def __init__(self, jd2):
        """设置表头"""
        self.head = jd2
        self.head.next = None
        self.tail = self.head

    def add(self, jd2):
        """增加节点"""
        self.tail.next = jd2
        self.tail = self.tail.next

    def view(self):
        """查找所有节点"""
        jd2 = self.head
        linkstr = ''

        while jd2 is not None:
            # 那些节点不是表尾
            if jd2.next is not None:
                linkstr = linkstr + str(jd2.data) + '-->'
            else:
                linkstr += str(jd2.data)
            jd2 = jd2.next
        print(linkstr)


# 声明节点：
jd1 = jd(7)
jd2 = jd("Hello")
jd3 = jd(8)
# 建立关系
x = Linklist(jd1)
x.add(jd3)
x.add(jd2)
# 查看链表
x.view()