Python风格单链表

面向接口的单链表

面向接口是python的特点之一，对于链表对象，我们如果想通过len(), in, +等方法使链表像list一样直观，就需要对len, contains等接口进行重写

节点类

class Node(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

链表类

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

在链表类中，实现的方法有

• insertEnd(self, val) 在链表尾添加元素
• insertIndex(self, index, val) 在指定的位置添加元素
• removeIndex(self, index) 删除指定位置的元素
• __len__(self) 返回链表的长度
• __contains__(self, item) 判断链表中是否存在某一元素
• __str__(self) 以字符串的形式打印链表
• `add(self, other)' 实现链表的+操作（other类型可为int、str或LinkedList)

contains方法

想要判断链表中是否包含某一元素，只需对链表进行一次遍历

def __contains__(self, item):
    probe = self.head
    while probe is not None:
        if probe.val == item:
            return True
        probe = probe.next
    return False

len方法

实现len方法对思路比较简单，仅需引入一个计数器count，每次节点后移时count += 1即可

count = 0
    probe = self.head
    while probe is not None:
        probe = probe.next
        count += 1
    return count

str方法

对链表进行一次遍历，将各节点对val以str的形式加入到result中

 def __str__(self):
    result = ""
    probe = self.head
    while probe.next is not None:
        result += str(probe.val) + "--->"
        probe = probe.next
    result += str(probe.val)
    return result

insertEnd(在尾端添加节点)

在链表尾添加节点，要找到链表的最后一个节点，使该节点的next指向要添加的节点

 def insertEnd(self, val):
    node = Node(val)
    probe = self.head
    while probe.next is not None:
        probe = probe.next
    probe.next = node

insertIndex(在第index个位置添加新的节点)

此方法需要考虑到两种情况

• index==0，此时，新节点应作为链表的头节点，之前的头节点则变为当前头节点的next节点
• 其余情况，找到第index-1节点，待添加节点的next指向原index节点，原index-1节点的next指向新节点

def insertIndex(self, index, val):
    node = Node(val)
    if index == 0:
        node.next = self.head
        self.head = node
    else:
        probe = self.head
        count = 0
        while probe.next is not None and count < index - 1:
            probe = probe.next
            count += 1
        node.next = probe.next
        probe.next = node

removeIndex(删除第index个位置的节点)

此方法要考虑到三种情况

• index=0时，链表头节点变为原头节点的next节点
• index为链表长度时，找到链表的倒数第二个节点，使其next变为None
• 其余情况，找到index-1个节点，使其next为原来的next.next

def removeIndex(self, index):
    probe = self.head
    count = 0
    if index == 0:
        self.head = self.head.next
    elif index == len(self):
        while probe.next is not None:
            probe = probe.next
            probe.next = None
    else:
        while probe.next is not None and count < index - 1:
            probe = probe.next
            count += 1
            probe.next = probe.next.next

add方法

add方法可让链表实现+操作，如果带添加的元素为str或int类型，则将其包装为一个节点，添加进链表的尾端，如果元素类型为链表，则将新的链表连写在原链表的尾端

def __add__(self, other):
    if type(other) == str:
        self.insertEnd(int(other))
    elif type(other) == int:
        self.insertEnd(other)
    elif type(other) == LinkedList:
        probe = self.head
        while probe.next is not None:
            probe = probe.next
        probe.next = other.head
    return self

测试

if __name__ == "__main__":
    linked_list = LinkedList(Node(0))
    linked_list + int(1) # 在链表末尾加入int类型1
    linked_list + int(2) # 在链表末尾加入int类型2
    linked_list + str(3) # 在链表末尾加入str类型3
    print("+1 2 3: ", linked_list)
    linked_list.insertIndex(1, 2) # 在index==1处加入val为2的元素
    print("insertIndex(1, 2): ", linked_list)
    linked_list.removeIndex(1) # 移除index==1的节点
    print("removeIndex(1): ", linked_list)
    print("3 in linked_list? ", 3 in linked_list) # 判断元素3是否在链表中
    print(linked_list)
    print("length: ", len(linked_list)) # 打印链表长度

    linked_list2 = LinkedList(Node(8))
    linked_list2 + int(9)
    new_list = linked_list + linked_list2 # 连接连个链表
    print("new_list: ", new_list)

测试结果