一、线性表综述
线性结构的特点就好比一串珠子，其特点是第一个节点只有一个后继，没有前驱，最后一个节点是只有一个前驱，没有后继。而其余的节点只有一个前驱和一个后继。说白了线性表就是一串。下方这个图就是线性表的示例图。中间蓝色的节点前方的是就是改点对应的前驱，后边就是改点对应的后继。从下方可以明确看出 head 没有前驱只有后继，而 tail 只有前驱没有后继。
线性表的物理结构可分为顺序存储结构和链式存储结构。顺序存储结构之所以称之为顺序存储结构因为每个线性表中节点的内存地址是连续的，而链式存储结构中线性表的节点的内存地址可以是不连续的。这也就是在C语言实现顺序存储线性表时先 Malloc 一块连续的区域，然后用来顺序的存储线性表。而链表中就可以不是连续的了，前驱与后继间的关系由指针连接。
如下所示。顺序存储的内存区块的内存地址是紧挨的，线性关系有相邻的内存地址所保存。当然下方我们是模拟的内存地址，就使用了 0x1, 0x2 等等来模拟。而链式存储的线性表，在物理存储结构中是不相邻的，仅仅靠内存地址无法去维持这种线性关系。所以就需要一个指针域来指向后继或者前驱节点的内存地址，从而将节点之间进行关联。在单向链式存储中，一个节点不仅仅需要存储数据，而且还要存储该节点下一个节点的内存地址，以便保持这种线性关系。
二、线性表的顺序存储
线性表的顺序存储，我们就使用 NSMutableArray 来实现，也就是使用 OC 中的可变数组类型来实现。我们就假设其存储的内存地址是连续的，当然数组中存储对象时要复杂的多，我们暂且假设其中的地址是连续的。下方的 lis t就是我们的顺序线性表，count 存储的是已经存入到线性表中的元素个数，而 capacity 则是记录线性表整个容量的大小。当然上述三个属性都是 private 的，而下方的计算属性 length 是 internal 类型的，供外界访问，返回线性表元素的个数。
class SequenceList {
fileprivate var list: NSMutableArray
fileprivate var count = 0
fileprivate var capacity = 0
// 元素个数
var length: Int {
get {
return count
}
}
init(capacity: Int) {
self.capacity = capacity
self.list = NSMutableArray(capacity: capacity)
}
}
1. 往顺序线性表中插入数据
在下图中，我们往AB与CD之间插入一个M。在插入M之前我们需要做的事情就是将CD整体往后移动一个位置，为M腾出一个位置，然后再讲M这个元素进行插入。
/**
根据下标插入值
- parameter item: 要插入的值
- parameter index: 下标
- returns: 返回插入结果，true or false
*/
func insert(_ item: String, index: Int) -> Bool {
if !checkIndex(index) {
return false
}
var i = count
while i > index {
list[i] = list[i-1]
i -= 1
}
list[index] = item;
count += 1
return true
}
首先检查 index 的合法性，检查 index 是否在合理范围内，然后将 index 后的元素依次往后移动，然后将元素插入即可。
2. 顺序线性表的元素移除
上述在插入之前是相应的元素往后移，腾出 index 位置。而移除特定索引的元素时，是相应的元素左移，覆盖掉要删除的元素，然后将最后一个元素进行移除掉。
/**
根据下标移除元素
- parameter index: 下标
- returns: 是否移除成
*/
func removeItme(_ index: Int) -> Bool {
if !checkIndex(index) {
return false
}
for i in index..<count-1 {
list[i] = list[i+1]
}
count -= 1
list.removeLastObject()
return true
}
/**
检查index是否合法
- parameter index: 索引
- returns: true合法，false不合法
*/
func checkIndex(_ index: Int) -> Bool {
if index < 0 || index > count {
print("index非法，请进行检查")
return false
}
return true
}
三、线性表的单链存储
1. 单向链表的创建
在链表创建之前，我们得先创建节点的类，因为链表是多个节点的连接。下方这个 OneDirectionLinkListNote 类就是单向链表的节点类。其中的 data 属性存储的是该节点所存储的数据，而变量 next 就是指向下一个节点的指针，链表中节点间的关系由 next 指针所关联。 init 和 deinit 就是该类的构造和析构函数
/// 单向链表的节点
class OneDirectionLinkListNote {
var data: AnyObject
var next: OneDirectionLinkListNote?
init(data: AnyObject = "" as AnyObject) {
self.data = data
}
deinit{
print("\(self.data)释放", separator: "", terminator: ",")
}
}
2.链表协议的创建
在创建链表之前，我们可以先创建一个链表协议 ListProtocalType 。在 ListProtocalType 协议中定义了链表所必须的方法，无论是单向链表还是双向链表都要遵循该协议。其实这就是“面向接口”的体现。单向链表与双向链表都遵循了这协议，那么说明这两种链表对外的接口是一致的，这样便于程序的维护，这也是面向接口编程的好处。下方就是我们事先定义好的 ListProtocalType 协议的部分内容。
下方协议中只给出了方法的定义，未给出具体实现。所有链表都要遵循该协议， ListProtocalType 中定义了链表结构所必须的方法。可以说下方这个协议就是链表的大纲。
protocol ListProtocalType {
func count() -> UInt
/**
根据数组正向创建链表
- parameter items: 数组
- returns: true-创建成功， false-创建失败
*/
func forwardDirectionCreateList(items: Array<AnyObject>) -> Bool
/**
根据数组逆向创建数组
- parameter items: 数组
- returns: true-创建成功， false-创建失败
*/
func reverseDirectionCreateList(items: Array<AnyObject>) -> Bool
/**
往链表前方追加元素
- parameter item: 所追加的元素
- returns: true-追加成功，false-追加失败
*/
func addItemToTail(item: AnyObject) -> Bool
/**
往链表后方追加元素
- parameter item: 所追加的元素
- returns: true-追加成功，false-追加失败
*/
func addItemToHead(item: AnyObject) -> Bool
/**
根据指定索引来插入item
- parameter item: 插入链表中的元素
- parameter index: 要插入的位置（0-length）
- returns: true-插入成功，false-插入失败
*/
func insertItem(item: AnyObject, index: UInt) -> Bool
/**
正向移除链表中所有的数据
*/
func removeAllItemFromHead()
/**
逆向移除链表中所有的数据
*/
func removeAllItemFromLast()
/**
移除第一个元素
- returns: 移除成功就返回节点数据，如果移除失败则返回nil
*/
func removeFirstNote() -> AnyObject?
/**
移除最后一个节点
- returns: 被移除的节点值
*/
func removeLastNote() -> AnyObject?
/**
根据索引移除节点
- parameter index: 索引
- returns: 被移除的节点值
*/
func removeItme(index: UInt) -> AnyObject?
/**
单向链表的遍历
*/
func display()
/**
检查index是否合法
- parameter index: 索引
- returns: true合法，false不合法
*/
func checkIndex(index: UInt) -> Bool
}
3.单向链表的构建
下方就是我们单向链表类的属性和构造函数。headNote 就是我们链表的头结点，而 tailNote 是我们链表的尾结点。 length 就是我们链表的长度，也就是我们链表中元素的个数。一个空链表中 tailNote = headNote 。
class OneDirectionLinkList: ListProtocalType {
var headNote: OneDirectionLinkListNote?
var tailNote: OneDirectionLinkListNote?
var length: UInt
init() {
self.headNote = OneDirectionLinkListNote()
self.tailNote = self.headNote
self.length = 0
}
}
下方这个截图中就是正向创建链表，其实就是将新创建的数据往链表的尾部插入，然后更新一下 tail 的位置即可。关键步骤就两步，第一步是 tail->next = newNode ，第二步是 tail = newNode 。插入步骤如下所示：
往链表的头部插入元素。该过程也是由关键的两步组成，第一步就是 newNode->next = head->next ，第二步是 head->next = newNode 。经过这两步我们就可以把元素插入到头结点的后方了。
正向创建数组
/**
根据数组正向创建链表
- parameter items: 数组
- returns: true-创建成功， false-创建失败
*/
func forwardDirectionCreateList(items: Array<AnyObject>) -> Bool {
for item in items {
if !self.addItemToTail(item: item) {
return false
}
}
return true
}
/**
往链表前方追加元素
- parameter item: 所追加的元素
- returns: true-追加成功，false-追加失败
*/
func addItemToTail(item: AnyObject) -> Bool {
let newLinkListNote = OneDirectionLinkListNote(data: item)
if self.tailNote == nil {
return false
}
self.tailNote?.next = newLinkListNote
self.tailNote = newLinkListNote
self.length += 1
return true
}
逆向创建数组
/**
根据数组逆向创建数组
- parameter items: 数组
- returns: true-创建成功， false-创建失败
*/
func reverseDirectionCreateList(items: Array<AnyObject>) -> Bool {
for item in items {
if !self.addItemToHead(item: item) {
return false
}
}
return true
}
/**
往链表后方追加元素
- parameter item: 所追加的元素
- returns: true-追加成功，false-追加失败
*/
func addItemToHead(item: AnyObject) -> Bool {
let newLinkListNote = OneDirectionLinkListNote(data: item)
if self.headNote == nil {
return false
}
newLinkListNote.next = headNote?.next
self.headNote?.next = newLinkListNote
self.length += 1
if length == 1 {
self.tailNote = newLinkListNote;
}
return true
}
4.单向链表元素的移除
要想移除单向链表中的一个元素，首先我们得找到被移除结点的前驱的位置，比如是 pre 。当前移除的元素是 remove ，让我我们让 pre->next = remove->next , 然后再执行 remove->next = nil 。经过上面这些步骤， remove 这个结点就与链表脱离关系了。示意图如下所示。
/**
根据索引移除节点
- parameter index: 索引
- returns: 被移除的节点值
*/
func removeItme(index: UInt) -> AnyObject? {
if self.headNote?.next == nil {
print("链表为空")
return nil //链表为空
}
if !self.checkIndex(index: index) {
return nil
}
var cursor = self.headNote //遍历节点的游标
var preCursor = self.headNote //记录一下cursor前面的节点
for i in 0..<self.length { //寻找移除的节点的位置，以及前驱
preCursor = cursor
cursor = cursor?.next
if index == i {
break
}
}
//对节点进行移除
preCursor?.next = cursor?.next
cursor?.next = nil
if index == self.length-1 {
self.tailNote = preCursor
}
self.length -= 1;
return cursor?.data;
}
四、双向链表
双向链表与单向链表相比多了一个指向前驱的节点。我们暂且称为将指向前驱的节点命名我 pre 指针。下方这个示意图就是双向链表的示意图，与单向链表相比，多了一个指向前驱的指针域。
下方示意图中就是往节点 A 后方插入一个节点 D 。主要分为四个步骤：
第一步是将 D 节点的 next 指针指向 A 节点 next 指针指向的节点，也就是 D->next = A->next ；
第二步是讲 D 节点的 pre 指针指向 A 节点，也就是 D->pre = A ；
第三步是将 A 的 next 指针指向 D ，也就是 A->next = D ；
最后将 D 节点的下一个节点的 pre 指针指向 D ，也就是 D->next->pre = D 。
经过这几步，我们就可以将节点 D 插入到 A 与 B 的中间。当然这个顺序不是一定的，只要能保证链的正确关联即可。
let newItme = DoublyLinkedListNote(data: item)
newItme.next = cursor?.next
if cursor?.next != nil{
cursor?.next?.pre = newItme
}
cursor?.next = newItme
newItme.pre = cursor
self.length += 1
2.双向链表元素的删除
下方这个截图就是删除 B 节点的示意图。首先将 B 节点前驱节点的 next 指针域指向 B 节点的后继，也就是 B->pre->next = B->next。 然后将 B 节点的后继节点的前驱指针指向 B 的前驱节点，对应着 B->next-pre = B->pre。最后将 B 的 next 和 pre 指针域置为 nil 。
/**
根据索引移除节点
- parameter index: 索引
- returns: 被移除的节点值
*/
func removeItme(index: UInt) -> AnyObject? {
if self.headNote?.next == nil {
print("链表为空")
return nil //链表为空
}
if !self.checkIndex(index: index) {
return nil
}
var cursor = self.headNote //遍历节点的游标
for i in 0..<self.length { //寻找移除的节点的位置，以及前驱
cursor = cursor?.next
if index == i {
break
}
}
let preCursor = cursor?.pre //记录一下cursor前面的节点
preCursor?.next = cursor?.next
if cursor?.next != nil {
cursor?.next?.pre = preCursor
}
cursor?.next = nil
cursor?.pre = nil
if index == self.length-1 {
self.tailNote = preCursor
}
self.length -= 1;
return cursor?.data;
}
