本帖最后由 yangrui 于 2018-12-27 12:40 编辑
单向链表
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。
链表的特点
1 单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小
2 结点的删除非常方便,不需要像线性结构那样移动剩下的数据
3 结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表
实现链表
能实现链表的语言有很多,这里我们使用Python语言来实现,不多说了,直接上代码:
[Python] 纯文本查看 复制代码 class Node(object):
"""节点"""
def __init__(self, data):
# 数据域
self.data = data
# 引用域
self.next = None
class SingleLinkList(object):
"""单向链表"""
def __init__(self):
self.__head = None
def is_empty(self):
"""判断链表是否为空"""
if self.__head == None:
return True
else:
return False
def add(self, data):
"""链表头部添加元素"""
node = Node(data)
node.next = self.__head
self.__head = node
def show(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
# 当cur指向当不为空,说明该节点是有效节点
print(cur.data, end=" --> ")
cur = cur.next
print()
def append(self, data):
"""链表尾部添加元素"""
cur = self.__head
if s.is_empty():
s.add(data)
return
# 当cur不是尾部节点的时候,我就偏移(cur = cur.next)
while cur.next != None:
cur = cur.next
# cur指向的就是尾部节点
node = Node(data)
cur.next = node
def length(self):
"""链表长度"""
cur = self.__head
count = 0
while cur != None:
# cur是一个有效的节点
count += 1
cur = cur.next
return count
def search(self, data):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
# cur是一个有效的节点
if cur.data == data:
return True
cur = cur.next
return False
def remove(self, data):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.data == data:
# cur当前节点就是我们要删除的节点
if cur == self.__head:
# 当前要删除的节点正好是头节点
self.__head = self.__head.next
return
pre.next = cur.next
return
# pre指向的就是cur的前置节点
pre = cur
cur = cur.next
def insert(self, index, data):
"""指定位置添加元素"""
# index <= 0
# 插入头部
if index <= 0:
s.add(data)
return
# index > s.length()-1
# 插入尾部
if index > s.length() - 1:
s.append(data)
return
cur = self.__head
for i in range(index-1):
cur = cur.next
# cur指向的就是第index-1个节点
node = Node(data)
node.next = cur.next
cur.next = node
if __name__ == "__main__":
s = SingleLinkList() # 测试
print("is empty: ", s.is_empty())
s.add(1)
s.add(2)
s.add(3)
s.show()
s.append(4)
s.show()
print("length: ", s.length())
print("search: ", s.search(11))
s.remove(2)
s.remove(3)
s.show()
s.insert(2, 10)
s.insert(1, 20)
s.show()
s.insert(-9, 777)
s.insert(99999, 666)
s.show()
|