双向链表
双向链表的node分为三个部分，前驱结点，数据，后继结点
image.png
设计一个带有头结点的双向链表，优点在于当需要插入新结点的时候，不需要考虑index为第一个的情况。只需特殊判断插入为最后一个结点时，后续为空。
image.png
设计结点
class Node {
var priod:Node?
var data:Int?
var next:Node?
}
双向链表插入，删除Swift实现
class LinkList {
//创建双向链表
func createLinkList() -> Node {
let l = Node()
l.priod = nil
l.next = nil
l.data = -1
var p = l
//新增10个结点
for index in 0...9 {
let temp = Node()
temp.priod = nil
temp.next = nil
temp.data = index
p.next = temp
temp.priod = p
p = temp
}
return l
}
//插入
func insert(linkList:Node, index i:Int, value:Int) {
let temp = Node()
temp.data = value
temp.priod = nil
temp.next = nil
//找到插入位置的前一个位置p
var j = 1
var p:Node? = linkList
while j < i && p != nil {
p = p?.next
j += 1
}
if p == nil {
return
}
//结点插入链表,先处理后继，再处理前驱
if p!.next == nil {
//当插入的结点为最后一个结点，temp的后继置空
p!.next = temp
temp.priod = p!
temp.next = nil
}else {
p!.next?.priod = temp
temp.next = p!.next
p!.next = temp
temp.priod = p!
}
}
//删除
func delete(linkList l:Node, index i:Int) {
var j:Int = 1
var p:Node? = l
//指针找到待删除的结点的前一个位置
while j < i && p != nil {
p = p?.next
j += 1
}
if j>i || p == nil {
return
}
let toDel = p!.next
p!.next = toDel!.next
//判断是否是最后一个结点
if toDel?.next != nil {
toDel?.next?.priod = p!
}
}
//打印链表
func show(linkList l:Node) {
var temp = l.next
if temp == nil {
print("双向链表为空")
return
}
while temp != nil {
print("data :: \(temp?.data ?? -1)")
temp = temp?.next
}
}
}
let link = LinkList()
let l = link.createLinkList()
link.show(linkList: l)
link.insert(linkList: l, index: 1, value: 99)
link.insert(linkList: l, index: 8, value: 99)
print("did Insert")
link.show(linkList: l)
link.delete(linkList: l, index: 4)
link.show(linkList: l)
运行结果
98E38995-938D-4299-9C85-AC0DCB336FB7.png
双向循环列表
相对于双向链表，双向循环列表的尾结点指向首结点
image.png
双向循环链表插入，删除Swift实现
//双向循环链表
class CycleLinkList {
func createLinkList() -> Node {
let l = Node()
l.next = l
l.priod = l
l.data = -1
var p = l
for index in 0...9 {
let temp = Node()
temp.data = index
p.next = temp
temp.priod = p
temp.next = l
p.priod = temp
p = p.next!
}
return l
}
//插入
func insert(linkList l:Node, index:Int, value:Int) {
var p:Node? = l
var i = 1
while i < index {
p = p?.next
i += 1
}
if i > index {
return
}
//创建
let temp = Node()
temp.data = value
temp.priod = p
temp.next = p?.next
p?.next = temp
if l !== temp.next {
temp.next?.priod = temp
}else {
l.priod = temp
}
}
//遍历
func show(linkList l:Node) {
var p = l.next
while p !== l {
print("data ==== \(p!.data ?? -1)")
p = p?.next
}
}
//删除
func delete(linkList l:Node, index:Int) {
var i = 1
var temp = l.next
//删除到只剩下首元结点了
if temp?.next === l {
return
}
//找到要删除的结点
while i < index {
temp = temp?.next
i += 1
}
//修改被删除结点的前驱的后继指针
temp?.priod?.next = temp?.next
//修改被删除结点的后继结点的前驱指针
temp?.next?.priod = temp?.priod
}
}
let cLink = CycleLinkList()
let cL = cLink.createLinkList()
cLink.show(linkList: cL)
cLink.insert(linkList: cL, index: 2, value: 99)
cLink.insert(linkList: cL, index: 5, value: 88)
print("did Insert")
cLink.show(linkList: cL)
cLink.delete(linkList: cL, index: 3)
print("did Delete")
cLink.show(linkList: cL)
运行结果
image.png
