鏈表分為單鏈表，雙向鏈表和循環(huán)鏈表
鏈表的時間復(fù)雜度
- 插入 O(n)
- 刪除 O(1)
- 隨機訪問 O(n)
單雙鏈表比較
雙向鏈表優(yōu)于單鏈表的優(yōu)點是 可以在O(1)時間復(fù)雜度的情況下找到前驅(qū)節(jié)點沪编。這樣可以某些情況下快速的插入刪除操作比單鏈表簡單高效恕出。但是空間復(fù)雜度要比單鏈表高
其實時間復(fù)雜度和空間復(fù)雜度球及，是相輔相成的，以時間換空間 或者以空間換時間。 比如復(fù)雜度O(n)的排序（桶排序 基數(shù)排序等）比快排冒泡排序快就是因為占用了大量的空間蒋荚，在空間內(nèi)基本上有序，這樣就降低了時間復(fù)雜度馆蠕。
數(shù)組和鏈表的比較
數(shù)組是連續(xù)的內(nèi)存塊期升， 一經(jīng)聲明就要占用整塊的內(nèi)存空間， 如果聲明一個很大的數(shù)組互躬， 但是內(nèi)存中沒有那么大的連續(xù)空間則聲明失敗播赁， 但是鏈表則不存在這些問題。
bb這么多吼渡，來看go版本的代碼實現(xiàn)（go中有一個庫叫container已經(jīng)實現(xiàn)了鏈表這種數(shù)據(jù)結(jié)果可以拿來直接使用）：
- 完成基本的準(zhǔn)備工作：
// 節(jié)點結(jié)構(gòu)體
type ListNode struct {
next *ListNode
value interface{}
}
// 鏈表結(jié)構(gòu)體
type LinkedList struct {
head *ListNode
length uint
}
func NewListNode(v interface{}) *ListNode {
return &ListNode{nil, v}
}
func (this *ListNode) GetNext() *ListNode {
return this.next
}
// 獲取節(jié)點值
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
}
// 在某節(jié)點前方插入
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
}
- 刪除操作
// 通過操作兩個指針找到對應(yīng)的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)
}
}
鏈表的操作基本上實現(xiàn)。
如何讓鏈表能快速的查找坎背， 可以通過鏈表來實現(xiàn)跳表這種類似索引功能的數(shù)據(jù)結(jié)構(gòu)來增加查找速度竭缝。但是同樣的是以空間換時間。
判斷是否有環(huán)
func (this *LinkedList) HasCycle() bool {
// 快慢指針判斷是否有環(huán)
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++ {
// 先把前一半數(shù)據(jù)裝載到數(shù)組 進(jìn)行比較
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
}
