面向接口的单链表
面向接口是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)
测试结果
