線性表
零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列鸭蛙。
線性表的結(jié)構(gòu)
- 順序存儲(chǔ)
- 鏈?zhǔn)酱鎯?chǔ)
順序存儲(chǔ)結(jié)構(gòu)
用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素姨伤，因?yàn)榈刂肥沁B續(xù)的熙暴，順序存儲(chǔ)結(jié)構(gòu)元素讀取很快肌幽，但是這個(gè)結(jié)構(gòu)的線表進(jìn)行插入以及刪除等操作涉及到的元素的地址都要進(jìn)行變換贪庙，都很不方便，于是衍生出下面那個(gè)鏈?zhǔn)降慕Y(jié)構(gòu)团赁。
一個(gè)圖：
34567的存儲(chǔ)位置都要變更育拨。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）
鏈表的兩種結(jié)構(gòu)
- 單向鏈表：每一個(gè)節(jié)點(diǎn)的只有下一個(gè)節(jié)點(diǎn)的引用
- 雙向鏈表：每一個(gè)節(jié)點(diǎn)有前一個(gè)和后一個(gè)節(jié)點(diǎn)的引用
每一個(gè)鏈表都有頭節(jié)點(diǎn)以及尾節(jié)點(diǎn)：
實(shí)現(xiàn)一個(gè)雙向鏈表
推薦研讀Swift Algorithm Club: Swift Linked List Data Structure
構(gòu)造一個(gè)節(jié)點(diǎn)類
public class Node{
var value : String
init(value:String){
self.value = value
}
}
value 可以是任意的數(shù)據(jù)類型，根據(jù)鏈表的用途來(lái)定然痊。在最后一個(gè)章節(jié)用泛型來(lái)改造這個(gè)數(shù)據(jù)結(jié)構(gòu)。
加入對(duì)下一個(gè)節(jié)點(diǎn)的引用
public class Node{
var next : Node?
var value : String
init(value:String){
self.value = value
}
}
加入對(duì)上一個(gè)節(jié)點(diǎn)的引用
public class Node{
var next : Node?
weak var previous : Node?
var value : String
init(value:String){
self.value = value
}
}
建立一個(gè)鏈表類
public class List {
fileprivate var head : Node?
private var tail : Node?
public var isEmpty : Bool{
return head == nil
}
public var head : Node?{
return head
}
public var tail : Node?{
return tail
}
}
讓鏈表類可以添加節(jié)點(diǎn)元素
public class List {
fileprivate var head : Node?
private var tail : Node?
public var isEmpty : Bool{
return head == nil
}
public var head : Node?{
return head
}
public var tail : Node?{
return tail
}
public func append(value:String){
let newNode = Node(value:value)
if let tailNode = tail{
newNode.previous = tailNode
tailNode.next = newNode
}else{
head = newNode
}
tail = newNode
}
}
List 類的實(shí)踐
首先添加一個(gè) List 的 extension 協(xié)助打印輸出
extension List{
public var description : String{
var text = "["
var node = head
while node != nil{
text += "\(node!.value)"
node = node!.next
if node != nil {
text += " , "
}
}
return text + "]"
}
}
let listt = List()
listt.append(value:"熊大")
listt.append(value:"熊二")
listt.append(value:"周末")
listt.append(value:"蛋蛋")
print(listt.description)
打印結(jié)果:
[熊大 , 熊二 , 周末 , 蛋蛋]
根據(jù)下標(biāo)讀取鏈表節(jié)點(diǎn)
由于鏈表的性質(zhì)屉符，從頭結(jié)點(diǎn)開始讀取剧浸，直到讀到對(duì)應(yīng)的下標(biāo)停止并返回相應(yīng)的節(jié)點(diǎn)锹引。
給 List 類添加一個(gè)讀取下標(biāo)對(duì)應(yīng)節(jié)點(diǎn)函數(shù)：
public func nodeAt(index:Int) -> Node? {
if index >= 0 {
var node = head
var i = index
while node != nil {
if i == 0 {
return node
}
i -= 1
node = node!.next
}
}
return nil
}
清空鏈表
只要將首節(jié)點(diǎn)與尾節(jié)點(diǎn)置為 nil 整個(gè)鏈表就會(huì)被置空。
給 List 添加函數(shù)：
public func removeAll() {
head = nil
tail = nil
}
移除其中某個(gè)節(jié)點(diǎn)
移除節(jié)點(diǎn)的三種情況：
- 移除首節(jié)點(diǎn)：如圖變更 Head 指針以及 Node1 的 previous 指針
- 移除尾節(jié)點(diǎn)：如圖變更 Tail 指針以及 Node2 的 next 指針指為 nil唆香。
- 移除非首尾節(jié)點(diǎn)：如圖只需要變更被移除的 Node1 節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn) Node0 的 next 指針指向 Node2嫌变，Node2 的 previous 指針指向 Node0，那么 Node1 節(jié)點(diǎn)就已經(jīng)脫離了鏈表躬它。
Screen Shot 2017-02-07 at 10.41.06 AM.png
給 List 添加移除節(jié)點(diǎn)函數(shù)：
public func remove(node: Node){
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
}else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
}
在進(jìn)行一次實(shí)踐
代碼：
let list = List()
list.append(value:"熊大")
list.append(value:"熊二")
list.append(value:"周末")
list.append(value:"蛋蛋")
print(list.description)
let node = list.nodeAt(index:1)
list.remove(node:node!)
print(list.description)
list.removeAll()
print(list.description)
輸出：
[熊大 , 熊二 , 周末 , 蛋蛋]
[熊大 , 周末 , 蛋蛋]
[]
使用泛型來(lái)改造這個(gè)鏈表類
改造節(jié)點(diǎn) Node 類
public class Node<T>{
var next : Node<T>?
weak var previous : Node<T>?
var value : T
init(value:T){
self.value = value
}
}
改造鏈表 List 類
public class List<T> {
fileprivate var head : Node<T>?
private var tail : Node<T>?
public var isEmpty : Bool{
return head == nil
}
public var first : Node<T>?{
return head
}
public var last : Node<T>?{
return tail
}
public func append(value:T){
let newNode = Node(value:value)
if let tailNode = tail{
newNode.previous = tailNode
tailNode.next = newNode
}else{
head = newNode
}
tail = newNode
}
public func nodeAt(index:Int) -> Node<T>? {
if index >= 0 {
var node = head
var i = index
while node != nil {
if i == 0 {
return node
}
i -= 1
node = node!.next
}
}
return nil
}
public func removeAll() {
head = nil
tail = nil
}
public func remove(node: Node<T>){
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
}else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
}
}
實(shí)踐
利用泛型特性改造之后腾啥，這個(gè)鏈表類則可以儲(chǔ)存任意類型的值，比較靈活冯吓。
輸入：
let list = List<String>()
list.append(value:"熊大")
list.append(value:"熊二")
list.append(value:"周末")
list.append(value:"蛋蛋")
輸出：
[熊大 , 熊二 , 周末 , 蛋蛋]
