链表是一种常见的数据结构,属于线性表的一种,但不会按照线性的顺序存储数据。
由于不按照顺序存储,链表在存储的时候是O(1)的复杂度。
链表包含:单向链表、双向链表、循环链表、块状链表
本文主要是单向链表的实践,也是链表中最简单的一种,它包含了两个域,一个用于数据存储,一个指向下一个节点,而最后一个节点指向None。
单向链表只可以往一个方向遍历,这也是名字的由来。
实践代码:
# -*- encoding: utf-8 -*-
"""
@File : singleLinkedList
@Author : TopAbu.com
@Software: IntelliJ IDEA
"""
# 1.定义节点类:item、next
# 2.定义单向链表类:定义一个属性保存头节点(需要根据头节点获取后续所有节点)
class Node(object):
name = '节点类'
def __init__(self, item):
self.item = item
self.next = None
def __repr__(self):
return str(self.item)
class SingleLinkedList(object):
name = '单向链表'
def __init__(self):
self.__head = None
def is_empty(self):
'''判断是否为空'''
return self.__head is None
def length(self):
'''返回链表的长度'''
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
'''打印链表中的每一个元素'''
cur = self.__head
while cur is not None:
print(cur.item)
cur = cur.next
def search(self, item):
'''查找某一元素是否在链表中'''
cur = self.__head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
def add(self, item):
'''链表头部添加元素'''
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
'''在尾部添加元素'''
node = Node(item)
if self.is_empty():
self.__head = node
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, item, pos):
'''
在指定位置添加元素
item -> 元素
pos -> 插入位置
'''
if pos <= 0:
self.add(item)
elif pos > (self.length() - 1):
self.append(item)
else:
count = 0
cur = self.__head
node = Node(item)
while count < (pos - 1):
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, item):
'''删除节点,默认删除一个元素'''
cur = self.__head
pre = None
while cur is not None:
if cur.item == item:
if cur == self.__head:
self.__head = cur.next
else:
cur.next = None
pre.next = cur.next
return
pre = cur
cur = cur.next
if __name__ == '__main__':
ll = SingleLinkedList()
print(ll.is_empty())
print(ll.length())
ll.add(1)
print(ll.search(1))
ll.append('a')
ll.add('b')
ll.insert('p', 2)
print('*'*20)
ll.travel()
print('*'*20)
ll.remove('p')
ll.travel()
文章评论