单链表的实现

结点定义

首先需要定义结点类Node，就是这么朴实无华。

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

单链表定义

然后就是整个单链表的定义了。

构造函数

class LinkedList():

    def __init__(self):
        self.__head = Node()
        self.__length = 0

将头结点和长度作为私有变量

基本操作

def length(self):
    return self.__length

def isEmpty(self):
    return self.__length == 0

def append(self, Node):
    if self.__length == 0:
        self.__head = Node
    else:
        p = self.__head
        while p.next:
            p = p.next
        p.next = Node
    self.__length += 1

def appendValue(self, value):
    node = Node(value)
    self.append(node)

def getHead(self):
    return self.__head

进阶操作

def display(self):
    s, p = [], self.__head
    for _ in range(self.__length):
        s.append(p.data)
        p = p.next
    # print(s)
    return "->".join(map(str, s))

def appendList(self, l):
    for i in l:
        self.append(i)

def appendListValue(self, l):
    for i in l:
        self.appendValue(i)

def addFirst(self, Node):
    Node.next = self.__head
    self.__head = Node
    self.__length += 1

def addFirstValue(self, value):
    self.addFirst(Node(value))

def index(self, value):
    cnt, p, flag = 0, self.__head, False
    while p:
        if p.data != value:
            p = p.next
            cnt += 1
        else:
            flag = True
            break
    return cnt if flag else -1

def insert(self, Node, pos):
    if pos <= 0:
        self.addFirst(Node)
    elif pos > self.__length:
        self.append(Node)
    else:
        p = self.__head
        for _ in range(pos-1):
            p = p.next
        p.next, Node.next = Node, p.next
        self.__length += 1

def delPos(self, pos):
    if pos < 0 or pos >= self.__length:
        print("Inavlid Pos!")
    elif pos == 0:
        self.__head = self.__head.next
        self.__length -= 1
    else:
        p = self.__head
        for _ in range(pos-1):
            p = p.next
        p.next = p.next.next
        self.__length -= 1

def delValue(self, value):
    pos = self.index(value)
    if pos == -1:
        print("Value Not Found!")
    else:
        self.delPos(pos)

这里实现了输出链表，插入数组，索引，插入指定位置和删除结点的操作。

测试代码

最后给个测试代码。

def testLinkLisk():
    l = LinkedList()
    print(l.isEmpty())
    l.append(Node(2))
    l.appendValue(3)
    l.appendListValue([4, 5, 6, 1, 2, 10])
    l.addFirst(Node(0))
    l.addFirstValue(9)
    print(l.length())
    print(l.display())
    # l.insert(Node(11),9)
    # l.delPos(0)
    l.delValue(1)
    print(l.length())
    print(l.display())
    print(l.index(2))