-
定义
链表像数组一样，也是一些数据的集合。
但是链表不像数组一样，内部的元素必须存储在相邻连续的一大块内存中，而链表中的数据是松散的存储在内存的各个位置的，对存储元素的内存没有连续性的要求。
链表中的每个元素也称为节点，节点之间通过 Link 相关联。
- 如果在链表中，每个节点（除了最后一个节点）都有一个指向后一个节点的指针，这种叫单向链表（如图1）
- 如果在链表中，除了每个节点（除了最后一个节点）都有一个指向后一个节点的指针外，同时每个节点（除了第一个节点）都有一个指向前一个节点的指针，这种叫做双向链表（如图2）
- 其他还有循环链表等
1.png
2.png
-
实现（双向链表）
- 定义节点
class LinkeListNode<T> {
var value: T
//3
//前驱 1
weak var previous: LinkeListNode?
//后继 2
var next: LinkeListNode?
init(_ value: T) {
self.value = value
}
}
这里实现一个双向链表，所以每个节点都有前驱和后继，(1,2)但是因为首节点和尾节点分别没有前驱和后继，所以讲两个变量设置为可选型，
(3)因为前后两个节点可能通过前驱和后继相互关联，所以讲前驱设置为weak引用，这样来防止节点间发生循环引用。
class LinkeList<T> {
typealias Node = LinkeListNode<T>
private var head: Node?
private var tail: Node?
var isEmpty: Bool {
return head == nil
}
///链表的第一个节点
var firstNode: Node? {
return head
}
///链表的最后一个节点
var lastNode: Node? {
return tail
}
///链表中节点总数
var count: Int {
guard var node = head else { return 0 }
var count = 1
while let next = node.next {
node = next
count += 1
}
return count
}
//MARK: -在链表最后增加新的节点
func append(_ value: T) {
let newNode = Node.init(value)
//列表不为空
if let lastNode = lastNode {
lastNode.next = newNode
newNode.previous = lastNod
}else {
head = newNode
}
//更新最后一个节点
tail = newNode
}
//MARK: -获得某个位置的节点
func node(atIndex index: Int) ->Node? {
guard var node = head else { return nil }
if index == 0 { return node }
for i in 1..<count {
guard let next = node.next else {
return nil
}
node = next
if index == i {
return node
}
}
return nil
}
//MARK: -在某个位置插入新的节点
/// 如果越界则增加在链表的末尾
func insert(_ newNode: Node, atIndex index: Int) {
//如果为空
guard let _ = head else {
return head = newNode
}
//不为空
if index == 0 {
head?.previous = newNode
newNode.next = head
head = newNode
//超出范围，插在最后面
}else if index > count {
append(newNode.value)
}else {
let prev = self.node(atIndex: index-1)
let next = prev?.next
newNode.previous = prev
newNode.next = prev?.next
prev?.next = newNode
next?.previous = newNode
}
}
//MARK: -删除列表
func removeAll() {
head = nil
}
//MARK: -删除某个节点
func remove(_ node: Node) {
let next = node.next
if let prev = node.previous {
prev.next = next
next?.previous = prev
}else {
head = next
}
node.previous = nil
node.next = nil
}
func removeAt(_ index: Int) {
guard let node = node(atIndex: index) else {
return
}
remove(node)
}
//同数组的map方法
func map<U>(transform: (T) -> U) -> LinkeList<U> {
let link = LinkeList<U>()
var node = head
while node != nil, let value = node?.value {
link.append(transform(value))
node = node?.next
}
return link
}
//同数组的filter方法
func filter(predicate: (T) -> Bool) -> LinkeList<T> {
let link = LinkeList<T>()
var node = head
while node != nil, let value = node?.value {
if predicate(value) {
link.append(node!.value)
}
node = node!.next
}
return link
}
}
上面就是双向列表的简单实现了，虽然在实际的编程过程中，我们很少去直接创建链表，然后去应用，但是还是有了解的必要的。
- 链表和数组的对比
从上面的实现我们可以看出，在查询链表中的某个节点时的时间复杂度为O(n)，而数组中查询的时间复杂度为O(1)。
但是在删除及插入操作时，链表的时间复杂度为O(1)，而我们知道数组中删除和插入的时间复杂度为O(n)。
