链表是实现线性表的链式存储结构的一种数据结构,链表根据结定义不同也有几个种类,分别为:
- 静态链表:用于没有指针类型的语言中。
- 单链表:链表的结点中只有指向直接后继结点的指针域。
- 循环链表:表中最后一个结点的指针指向头结点,整个链表形成一个环。
- 双向链表:每个数据结点中都有两个指针,分别指向直接后继和直接前驱。
以下的实例代码,都是以单链表为例的。
这篇文章的主要内容
- 链表的一些概念
- 链表的基本结构
- 链表的一些操作
概念
-
链表
用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的。数据元素间的逻辑顺序是通过结点中的指针域来实现。
-
结点
存储数据元素信息的域称为数据域,把存储后继位置或前驱结点的域称为指针域。这两部分就是链表中的一个节点。
基本结构
结点的基本结构:
class LinkedListNode {
var value: Int
var next: LinkedListNode?
public init(_ value: Int) {
self.value = value
self.next = nil
}
}
链表的接本结构:
class LinkedList {
var head: LinkedListNode? // 头结点
var tail: LinkedListNode? // 尾结点
}
常用操作
先在已经定义好了链表及结点的基本结构了,下面我们可以对链表做一些常见的操作。
增加
尾插法
func appendToTail(_ value: Int) {
let newNode = LinkedListNode(value)
if let last = tail {
last.next = newNode
tail = last.next
} else {
head = newNode
tail = head
}
}
头插法
func appendToHead(_ value: Int) {
let newNode = LinkedListNode(value)
if let first = head {
newNode.next = first
head = newNode
} else {
head = newNode
tail = head
}
}
中间插入
// 给链表增加了一个长度属性
var length: Int {
get {
var num = 0
var temp: LinkedListNode? = head
while let node = temp {
num += 1
temp = node.next
}
return num
}
}
func appned(_ value: Int, _ index: Int) {
if length == 0 {
// 链表本身为空,直接添加
appendToHead(value)
} else if index == 0 {
// 插入到头结点位置
let newNode = LinkedListNode(value)
newNode.next = head
head = newNode
} else if index < length && index > 0 {
// 找到需要插入位置的前一个结点
let newNode = LinkedListNode(value)
var temp = 1
var tempNode: LinkedListNode? = head
while let node = tempNode {
if temp == index {
newNode.next = node.next
node.next = newNode
break
}
tempNode = tempNode?.next
temp += 1
}
}
}
创建
利用尾插法直接将数组元素插入到链表末端
init(array: [Int]) {
array.forEach { appendToTail($0) }
}
删除
func remove(at index: Int) {
// 链表为空
if length == 0 {
return
} else if index == 0 {
head = head?.next
} else if index < length && index > 0 {
var tempNode: LinkedListNode?
var j = 0
var tempList: LinkedListNode? = head
while tempList?.next != nil && j < index-1 {
tempList = tempList?.next
j += 1
}
tempNode = tempList?.next
tempList?.next = tempNode?.next
}
}
查找
// 查找某个结点
func node(at index: Int) -> LinkedListNode? {
if length == 0 {
return nil
} else if index >= 0 && index < length {
var tempNode = head
var j = 0
while tempNode?.next != nil && j < index {
tempNode = tempNode?.next
j += 1
}
return tempNode
}
return nil
}
// 根据值查找
func nodes(_ value: Int) -> [LinkedListNode] {
var result: [LinkedListNode] = []
var tempNode = head
while let node = tempNode {
if node.value == value {
result.append(node)
}
tempNode = node.next
}
return result
}
反转
func reverse(_ head: LinkedListNode?) -> LinkedListNode? {
if head == nil || head?.next == nil {
return head
}
// 递归找到最后一个结点
let newHead = reverse(head?.next)
// 将最后一个结点前一个结点反转
head?.next?.next = head
// 断开最后一个结点
head?.next = nil
self.head = newHead
return newHead
}
过程说明:
为链表扩展一些操作函数
// 打印链表
func printSelf() {
var tempNode = head
while let node = tempNode {
print(node.value)
tempNode = tempNode?.next
}
}
func map(transform: (Int) -> Int) -> LinkedList {
let result = LinkedList()
var tempNode = head
while let node = tempNode {
result.appendToTail(transform(node.value))
tempNode = node.next
}
return result
}
func filter(predicate: (Int) -> Bool) -> LinkedList {
let result = LinkedList()
var tempNode = head
while let node = tempNode {
if predicate(node.value) {
result.appendToTail(node.value)
}
tempNode = node.next
}
return result
}
总结
结合上篇线性表的顺序存储结构与单链表结构进行对比:
-
存储方式
- 顺序存储用一段连续的存储单元依次存储线性表的数据元素。
- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。
-
时间性能
- 查找
- 顺序存储结构 O(1)
- 单链表结构 O(n)
- 插入和删除
- 顺序存储结构平均需要移动表长一半的元素 O(n)
- 单链表结构在找出某位置的指针后,插入和删除时间为O(1)
- 查找
-
空间性能
- 顺序存储结构需要预分配存储空间,分配大了浪费空间,分配小了易造成溢出。
- 单链表结构不需要预分配存储空间,只要有就可以分配,元素个数不受限制。