链表分为单链表，双向链表和循环链表
链表的时间复杂度
- 插入 O(n)
- 删除 O(1)
- 随机访问 O(n)
单双链表比较
双向链表优于单链表的优点是 可以在O(1)时间复杂度的情况下找到前驱节点。这样可以某些情况下快速的插入删除操作比单链表简单高效。但是空间复杂度要比单链表高
其实时间复杂度和空间复杂度，是相辅相成的，以时间换空间 或者以空间换时间。 比如复杂度O(n)的排序（桶排序 基数排序等）比快排冒泡排序快就是因为占用了大量的空间，在空间内基本上有序，这样就降低了时间复杂度。
数组和链表的比较
数组是连续的内存块， 一经声明就要占用整块的内存空间， 如果声明一个很大的数组， 但是内存中没有那么大的连续空间则声明失败， 但是链表则不存在这些问题。
bb这么多，来看go版本的代码实现（go中有一个库叫container已经实现了链表这种数据结果可以拿来直接使用）：
- 完成基本的准备工作：
// 节点结构体
type ListNode struct {
next *ListNode
value interface{}
}
// 链表结构体
type LinkedList struct {
head *ListNode
length uint
}
func NewListNode(v interface{}) *ListNode {
return &ListNode{nil, v}
}
func (this *ListNode) GetNext() *ListNode {
return this.next
}
// 获取节点值
func (this *ListNode) GetValue() interface{} {
return this.value
}
// 穿件新的链表
func NewLinkedList() *LinkedList {
return &LinkedList{NewListNode(0), 0}
}
- 链表的操作：
// 插入
func (this *LinkedList) InsertAfter(p *ListNode, v interface{}) bool {
if nil == p {
return false
}
// 断开p的next，然后插入新的next 再连接到一起
newNode := NewListNode(v)
oldNext := p.GetNext()
p.next = newNode
newNode.next = oldNext
this.length++
return true
}
// 在某节点前方插入
func (this *LinkedList) InsertBefore(p *ListNode, v interface{}) bool {
if nil == p || p == this.head {
return false
}
cur := this.head.next
pre := this.head
for nil != cur {
if cur == p {
break
}
pre = cur
cur = cur.next
}
newNode := NewListNode(v)
pre.next = newNode
newNode.next = cur
this.length++
return true
}
func (this *LinkedList) InsertToHead(v interface{}) bool {
return this.InsertAfter(this.head, v)
}
func (this *LinkedList) InsertToTail(v interface{}) bool {
cur := this.head
for nil != cur.next {
cur = cur.next
}
return this.InsertAfter(cur, v)
}
- 查找操作
func (this *LinkedList) FindByIndex(index uint) *ListNode{
if index >= this.length {
return nil
}
cur := this.head.next
var i uint = 0
for ; i<index; i++ {
cur = cur.next
}
return cur
}
- 删除操作
// 通过操作两个指针找到对应的p然后断开去掉p再重新连上。
func (this *LinkedList) DeleteNode(p *ListNode) bool {
if p == nil {
return false
}
cur := this.head.next
pre := this.head
for nil != cur {
if cur == p {
break
}
pre = cur
cur = cur.next
}
if nil == cur {
return false
}
pre.next = p.next
p = nil
this.length--
return true
}
- 打印
func (this *LinkedList) Print() {
cur := this.head.next
format := ""
for nil != cur {
format += fmt.Sprintf("%+v", cur.GetValue())
cur = cur.next
if nil != cur {
format += "->"
}
fmt.Println(format)
}
}
链表的操作基本上实现。
如何让链表能快速的查找， 可以通过链表来实现跳表这种类似索引功能的数据结构来增加查找速度。但是同样的是以空间换时间。
判断是否有环
func (this *LinkedList) HasCycle() bool {
// 快慢指针判断是否有环
if nil != this.head{
slow := this.head
fast := this.head.next
for nil != fast && nil != fast.next {
slow = slow.next
fast = fast.next.next
if slow == fast {
return true
}
}
}
return false
}
判断是否是回文字符串
func isPalindrome(l *LinkedList) bool {
lLen := l.length
if lLen == 0 {
return false
}
if lLen == 1 {
return true
}
s := make([]string, 0, lLen/2)
cur := l.head
for i := uint(1); i < lLen; i++ {
// 先把前一半数据装载到数组 进行比较
cur = cur.next
if lLen % 2 != 0 && i == (lLen/2 + 1) {
continue
}
if i <= lLen / 2 {
s = append(s, cur.GetValue().(string))
}else {
if s[lLen - 1] != cur.GetValue().(string) {
return false
}
}
}
return true
}
