家电维修网站建设,wordpress模板与主题的区别,营销网站建设费用,对中国建设银行网站的缺点一、什么是链表
链表是一种物理存储结构上非连续#xff0c;非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构是多式多样的#xff0c;当时通常用的也就是两种#xff1a; #xff08;1#xff09;第一种是无头非循环单向…一、什么是链表
链表是一种物理存储结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构是多式多样的当时通常用的也就是两种 1第一种是无头非循环单向链表 2第二种是带头循环双向链表
无头单向非循环列表结构简单一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构比如说哈希桶等等。带头双向循环链表结构最复杂一般单独存储数据。实际中经常使用的链表数据结构都是带头双向循环链表。这个结构虽然复杂但是使用代码实现后会发现这个结构会带来很多优势实现反而简单了。
二、链表和数组对比
2.1 链表和数组的区别
数组静态分配内存链表动态分配内存。数组在内存中是连续的链表是不连续的。数组利用下标定位查找的时间复杂度是O(1)链表通过遍历定位元素查找的时间复杂度是O(N)。数组插入和删除需要移动其他元素时间复杂度是O(N)链表的插入或删除不需要移动其他元素时间复杂度是O(1)。
2.2 数组的优缺点
数组的优点
随机访问性比较强可以通过下标进行快速定位。查找速度快
数组的缺点
插入和删除的效率低需要移动其他元素。会造成内存的浪费因为内存是连续的所以在申请数组的时候就必须规定七内存的大小如果不合适就会造成内存的浪费。内存空间要求高创建一个数组必须要有足够的连续内存空间。数组的大小是固定的在创建数组的时候就已经规定好不能动态拓展。
2.3 链表的优缺点
链表的优点
插入和删除的效率高只需要改变指针的指向就可以进行插入和删除。内存利用率高不会浪费内存可以使用内存中细小的不连续的空间只有在需要的时候才去创建空间。大小不固定拓展很灵活。
链表的缺点
查找的效率低因为链表是从第一个节点向后遍历查找。
三、单链表与双链表对比
单链表和双链表的区别
单链表的每一个节点中只有指向下一个结点的指针不能进行回溯适用于节点的增加和删除。双链表的每一个节点给中既有指向下一个结点的指针也有指向上一个结点的指针可以快速的找到当前节点的前一个节点适用于需要双向查找节点值的情况。
双链表相对于单链表的优点 删除单链表中的某个节点时一定要得到待删除节点的前驱得到其前驱的方法一般是在定位待删除节点的时候一路保存当前节点的前驱这样指针的总的的移动操作为2n次如果是用双链表就不需要去定位前驱所以指针的总的的移动操作为n次。 查找时也是一样的可以用二分法的思路从头节点向后和尾节点向前同时进行这样效率也可以提高一倍但是为什么市场上对于单链表的使用要超过双链表呢从存储结构来看每一个双链表的节点都比单链表的节点多一个指针如果长度是n就需要n*lenght32位是4字节64位是8字节的空间这在一些追求时间效率不高的应用下就不适用了因为他占的空间大于单链表的1/3所以设计者就会一时间换空间。
四、环形链表
4.1 判断是否有环
定义一个快指针和一个慢指针快指针一次走两步慢指针一次走两步会出现两种情况情况一指针走到了空的位置那就说明这个链表不带环。情况二两个指针相遇说明这个链表带环。
获得入环节点 如果不考虑空间复杂度可以使用一个map来记录走过的节点这个指针一直向后遍历如果遇到空说明这个链表不带环也就没有入环节点如果没有遇到空如果遇到第一个在map中存在的节点就说明回到了出发点这个节点就是环的入口节点。如果不建立额外的空间先使用快慢指针判断这个链表是否有环如果有环将相遇节点记录然后一个指针从链表的起始位置开始一次走一步另一个指针从记录的节点开始一次走一步当两个节点再次相遇这个相遇节点就是环的入口节点。
五、链表的简单实现
5.1 单链表实现
package Listtype listNode struct {val intnext *listNode
}func newNode(val int) *listNode {node : new(listNode)node.val valnode.next nilreturn node
}// NewList 初始化一个不带头结点的链表
func NewList(vals []int) *listNode {var fistNode *listNodevar curNode *listNodefor _, v : range vals {node : newNode(v)if curNode nil {fistNode nodecurNode fistNodecontinue}curNode.next nodecurNode curNode.next}return fistNode
}// FistAdd 头插
func FistAdd(fistNode *listNode, val int) *listNode{if fistNode nil {return fistNode}node : newNode(val)node.next fistNodereturn node
}// LastAdd 尾插
func LastAdd(fistNode *listNode, val int) {if fistNode nil {return}curNode : fistNodefor curNode.next ! nil {curNode curNode.next}node : newNode(val)curNode.next nodereturn
}// IndexValAdd 在第一个指定值后插入若没有在链表尾部插入
// fistNode 链表第一个节点, indexVal 目标节点值, val 新节点值
func IndexValAdd(fistNode *listNode, indexVal, val int) {if fistNode nil {return}curNode : fistNodefor curNode.next ! nil curNode.val ! indexVal {curNode curNode.next}node : newNode(val)nextNode : curNode.nextnode.next nextNodecurNode.next nodereturn
}// ChangVal 更改目标节点值若没有不做改动
// fistNode 链表第一个节点, indexVal 目标节点值, val 目标值
func ChangVal (fistNode *listNode, indexVal, tarVal int) {if fistNode nil {return}curNode : fistNodefor curNode ! nil curNode.val ! indexVal {curNode curNode.next}// 判断是走到最后都没有找到对应值还是找到对应值if curNode nil{return}curNode.val tarValreturn}// DelNode 删除指定节点若没有则不删除
func DelNode(fistNode *listNode, indexVal int) {if fistNode nil {return}curNode : fistNode// 查找要删除节点的前一个节点for curNode.next ! nil {nextNode : curNode.nextif nextNode.val indexVal {break}curNode curNode.next}if curNode.next nil {return}nextNode : curNode.nextcurNode.next nextNode.next}// Show 不带头节点查
func Show(node *listNode) []int {if node nil {return []int{}}valSlice : make([]int, 0, 4)curNode : nodefor curNode ! nil {valSlice append(valSlice, curNode.val)curNode curNode.next}return valSlice
}
测试验证
package mainimport (Data/Listfmt
)func main() {// 初始化一个链表fistNode : List.NewList([]int{1, 2, 3, 4, 5})fmt.Println(初始化一个链表 :,List.Show(fistNode))// 对链表进行头插fistNode List.FistAdd(fistNode, 0)fmt.Println(对链表进行头插 0 :,List.Show(fistNode))// 对链表进行尾插List.LastAdd(fistNode, 6)fmt.Println(对链表进行尾插 6 :,List.Show(fistNode))// 删除指定节点List.DelNode(fistNode, 3)fmt.Println(删除指定节点 3 :,List.Show(fistNode))List.DelNode(fistNode, 3)fmt.Println(删除指定节点 3 :,List.Show(fistNode))List.DelNode(fistNode, 3)fmt.Println(删除指定节点 7 :,List.Show(fistNode))// 在第一个指定值后插入List.IndexValAdd(fistNode, 4, 41)fmt.Println(在第一个指定值后插入若没有在链表尾部插入 4 41 :,List.Show(fistNode))List.IndexValAdd(fistNode, 7, 42)fmt.Println(在第一个指定值后插入若没有在链表尾部插入 7 42 :,List.Show(fistNode))// 更改目标节点值List.ChangVal(fistNode, 4, 40)fmt.Println(更改目标节点值 4 40 :,List.Show(fistNode))List.ChangVal(fistNode, 7, 43)fmt.Println(更改目标节点值 7 43 :,List.Show(fistNode))
}
5.2 双向循环链表的实现
package Listimport fmtfunc newCircleNode(val int) *listNode {node : new(listNode)node.val valnode.next nodereturn node
}func NewCircleList(vals []int) *listNode {var fistNode *listNodevar curNode *listNodefor _, v : range vals {if curNode nil {fistNode newCircleNode(v)curNode fistNodecontinue}node : newCircleNode(v)node.next fistNodecurNode.next nodecurNode curNode.next}return fistNode
}func isLastNode(fistNode *listNode, node *listNode) bool {return node.next fistNode
}// CircleFistAdd 头插
func CircleFistAdd(fistNode **listNode, val int) {if fistNode nil {return}curNode : *fistNodefor !isLastNode(*fistNode, curNode) {curNode curNode.next}node : newCircleNode(val)curNode.next nodenode.next *fistNode*fistNode node
}// CircleLastAdd 尾插
func CircleLastAdd(fistNode *listNode, val int) {if fistNode nil {return}curNode : fistNodefor !isLastNode(fistNode, curNode) {curNode curNode.next}node : newCircleNode(val)node.next fistNodecurNode.next node}// CircleIndexValAdd 在第一个指定值后插入若没有在链表尾部插入
func CircleIndexValAdd(fistNode *listNode, indexVal,val int) {if fistNode nil {return}curNode : fistNodefor !isLastNode(fistNode, curNode) curNode.val ! indexVal {curNode curNode.next}node : newCircleNode(val)node.next curNode.nextcurNode.next node}// CircleChangVal 更改目标节点值若没有不做改动
func CircleChangVal(fistNode *listNode, indexVal, tarVal int) {if fistNode nil {return}curNode : fistNodefor curNode.val ! indexVal !isLastNode(fistNode, curNode) {curNode curNode.next}if curNode.val indexVal {curNode.val tarValreturn}fmt.Printf(节点 %d 不存在\n, indexVal)
}// CircleDelNode 删除指定节点若没有则不删除
func CircleDelNode(fistNode *listNode, indexVal int) {if fistNode nil {return}curNode : fistNodefor curNode.next.val ! indexVal !isLastNode(fistNode, curNode) {curNode curNode.next}if curNode.next.val indexVal {curNode.next curNode.next.nextreturn}fmt.Printf(没有该节点 %d \n, indexVal)}// CircleShow 查看链表
func CircleShow(fistNode *listNode) {if fistNode nil {return}curNode : fistNodefor {if isLastNode(fistNode, curNode) {fmt.Printf(val:%d next:%d, curNode.val, curNode.next.val)break}fmt.Printf(val:%d next:%d - , curNode.val, curNode.next.val)curNode curNode.next}fmt.Println()
}测试验证
package mainimport (Data/Listfmt
)func main() {// 初始化一个环形链表circleFistNode : List.NewCircleList([]int{1, 2, 3})fmt.Println(初始化一个链表 :)List.CircleShow(circleFistNode)// 对链表进行头插List.CircleFistAdd(circleFistNode, 0)fmt.Println(对链表进行头插 0:)List.CircleShow(circleFistNode)// 对链表进行尾插List.CircleLastAdd(circleFistNode, 4)fmt.Println(对链表进行尾插 4 :)List.CircleShow(circleFistNode)// 删除指定节点fmt.Println(删除指定节点 3 :)List.CircleDelNode(circleFistNode, 3)List.CircleShow(circleFistNode)fmt.Println(删除指定节点 3 :)List.CircleDelNode(circleFistNode, 3)List.CircleShow(circleFistNode)fmt.Println(删除指定节点 7 :)List.CircleDelNode(circleFistNode, 7)List.CircleShow(circleFistNode)// 在第一个指定值后插入circleFistNode List.NewCircleList([]int{1, 2, 3})fmt.Println(初始化一个链表 :)List.CircleShow(circleFistNode)List.CircleIndexValAdd(circleFistNode, 2, 41)fmt.Println(在第一个指定值后插入若没有在链表尾部插入 2 41 :)List.CircleShow(circleFistNode)List.CircleIndexValAdd(circleFistNode, 7, 42)fmt.Println(在第一个指定值后插入若没有在链表尾部插入 7 42 :)List.CircleShow(circleFistNode)// 更改目标节点值circleFistNode List.NewCircleList([]int{1, 2, 3, 4})fmt.Println(初始化一个链表 :)List.CircleShow(circleFistNode)fmt.Println(更改目标节点值 3 40 :)List.CircleChangVal(circleFistNode, 3, 40)List.CircleShow(circleFistNode)fmt.Println(更改目标节点值 7 43 :)List.CircleChangVal(circleFistNode, 7, 43)List.CircleShow(circleFistNode)//
}
