基本数据结构:链表

链表是什么

链表的实现

必须明确指定链表的第一项的位置。当我们知道第一个位置，就可以知道第二个位置….外部的引用通常被称为链表的头。最后一个位置 要知道没有下一个项。

链表的节点(Node)

链表实现的基本的构造块是节点。每一个节点至少保存两个信息。首先，节点必须要有列表项本身，也就是数据字段；此外，每个节点必须保存下一个节点的引用。

# 节点
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

链表的构建

class LinkList:
    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