整理一下使用python3实现的部分单向链表的基本操作
链表的概念
链表(linked list)是由一组被称为结点(Node)的数据元素组成的数据结构。每个结点分为两部分：数据域和指针域，其中数据域存储结点的信息，指针域指向链表的下一个结点。在一个链表中，头结点(head)永远指向该链表的第一个结点，尾结点(tail)永远指向该链表的最后一个结点，该链表最后一个结点的指针域指向空(None)。
链表的基本操作
定义结点类
class Node:
def __init__(self,data):
self.data = data
self.next = None
定义链表类
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
检查链表的是否为空
def is_empty(self):
if self.head is None:
print("is empty")
return True
else:
print("no")
return
显示链表元素
def view(self):
current = self.head
while current is not None:
print(current.data)
current = current.next
在结尾处插入结点
def append(self,data):
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
显示链表长度
def size(self):
counter = 0
current = self.head
while current is not None:
counter = counter + 1
current = current.next
return counter
插入结点
def insert(self,index,data):
current = self.head
current_idx = 0
if current is None:
raise Exception("The linked list is an empty list")
if index is 0:
node = Node(data)
node.next = current
self.head = node
return
while current_idx < index-1:
current = current.next
if current is None:
raise Exception("the index exceed the length of list")
current_idx = current_idx + 1
node = Node(data)
node.next = current.next
current.next = node
if node.next is None:
self.tail = node
删除结点
def remove(self,index):
current = self.head
current_idx = 0
if self.head is None:
raise Exception("the linked list is an empty list")
while current_idx < index-1:
current = current.next
if current is None:
raise Exception("the index exceed the length of list")
current_idx = current_idx + 1
if index == 0:
self.head = current.next
current = current.next
return
if self.head is self.tail:
self.head = None
self.tail = None
return
current.next = current.next.next
if current.next is None:
self.tail = current
完整代码及测试
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
if self.head is None:
print("is empty")
return True
else:
print("no")
return
def view(self):
current = self.head
while current is not None:
print(current.data)
current = current.next
def append(self,data):
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def size(self):
counter = 0
current = self.head
while current is not None:
counter = counter + 1
current = current.next
return counter
def insert(self,index,data):
current = self.head
current_idx = 0
if current is None:
raise Exception("The linked list is an empty list")
if index is 0:
node = Node(data)
node.next = current
self.head = node
return
while current_idx < index-1:
current = current.next
if current is None:
raise Exception("the index exceed the length of list")
current_idx = current_idx + 1
node = Node(data)
node.next = current.next
current.next = node
if node.next is None:
self.tail = node
def remove(self,index):
current = self.head
current_idx = 0
if self.head is None:
raise Exception("the linked list is an empty list")
while current_idx < index-1:
current = current.next
if current is None:
raise Exception("the index exceed the length of list")
current_idx = current_idx + 1
if index == 0:
self.head = current.next
current = current.next
return
if self.head is self.tail:
self.head = None
self.tail = None
return
current.next = current.next.next
if current.next is None:
self.tail = current
node1 = Node(10)
linkedlist = LinkedList()
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
linkedlist.insert(0,4)
linkedlist.remove(3)
linkedlist.view()
