# 定义链表节点
class Node(object):
def __init__(self, data, n=None):
self.data = data
self.next = n
# 定义链表及其增删改查
class LinkList(object):
def __init__(self):
# 初始化空链表
self.head = None
self.tail = None
self.length = 0
def is_empty(self):
# 判断链表是否为空
return self.length == 0
def append(self, dataOrNode):
"""
在尾部添加数据
:param dataOrNode: Data or Node obj
:return: True or None
"""
# 判断是一个数据还是Node对象
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if self.length == 0:
# 判断是一个空链表, 直接赋值
self.head = item
else:
# 将旧尾部节点的next指向新增加的数据
old_tail = self.tail
old_tail.next = item
self.tail = item
self.length += 1
return True
def delete(self, index):
"""
删除指定位置的数据
:param index: 位置
:return: True or False
"""
if self.is_empty():
print("this chain table is empty.")
return False
if index < 0 or index >= self.length:
print("error: out of index.")
return False
if index == 0:
# 直接删除第一个数据
self.head = self.head.next
self.length -= 1
return True
else:
j = 0
node = self.head
prev = self.head
# 从头开始遍历，遍历到指定位置，然后删除数据
while node.next and j < index:
prev = node
node = node.next
j += 1
if j == index:
prev.next = node.next
self.length -= 1
return True
if index == self.length - 1:
self.tail = prev
def insert(self, index, dataOrNode):
"""
在指定位置插入数据
:param index: 位置
:param dataOrNode: Data or Node Obj
:return: True or False
"""
if self.is_empty():
print("this chain table is empty")
return False
if index < 0 or index >= self.length:
print("error: out of index")
return False
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if index == 0:
# 在首部直接插入数据
item.next = self.head
self.head = item
self.length += 1
else:
j = 0
node = self.head
prev = self.head
# 从头开始遍历，遍历到指定位置，然后插入数据
while node.next and j < index:
prev = node
node = node.next
j += 1
if j == index:
item.next = node
prev.next = item
self.length += 1
return True
def update(self, index, data):
"""
更新指定位置的数据
:param index: 位置
:param data: 数据
:return: True or False
"""
if self.is_empty() or index < 0 or index >= self.length:
print("error: out of index")
return False
j = 0
node = self.head
# 从头开始遍历，遍历到指定位置，然后更新数据
while node.next and j < index:
node = node.next
j += 1
if j == index:
node.data = data
return True
return False
def get_item(self, index):
"""
获取指定位置的数据
:param index:
:return:
"""
if self.is_empty() or index < 0 or index >= self.length:
print("error: out of index")
return
j = 0
node = self.head
while node.next and j < index:
node = node.next
j += 1
if j == index:
return node.data
def clear(self):
"""
删除所有数据
:return:
"""
self.head = None
self.length = 0
return True
def __len__(self):
return self.length
def __getitem__(self, item):
# 使用[]获取实例属性 如obj[item], python会自动调用__getitem__方法;
return self.get_item(item)
def __setitem__(self, key, value):
# 使用[]设置实例属性 如obj[key] = value, python会自动调用__setitem__方法;
return self.update(key, value)
if __name__ == '__main__':
link = LinkList()
for i in range(5):
link.append(i)
print("初始化后,链表长度为:", len(link))
for i in range(len(link)):
print("初始化数据:", link.get_item(i))
print("删除指定位置数据:", link.delete(0))
print("删除指定数据后，链表长度为:", len(link))
for i in range(len(link)):
print("删除后的数据为:", link.get_item(i))
print("指定位置插入数据:", link.insert(1, 100))
print("插入数据后的链表长度:", len(link))
for i in range(len(link)):
print("插入后的数据:", link.get_item(i))
print("更新指定数据", link.update(1, 200))
# 更新数据
link[1] = 100
# 获取数据
print(link[1])