go語言雙向鏈表及其常用方法的實(shí)現(xiàn)

目的

  • 完善鏈表相關(guān)的概念，實(shí)現(xiàn)雙向鏈表的常用方法。

1、雙向鏈表的特點(diǎn)和初始化

1.1 雙向鏈表的存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

1.2 雙向鏈表的特性

  • 我覺得用下面這行代碼最能夠展示雙向鏈表的特性
p->next->prior = p->prior->next = p

1.3 雙向鏈表的結(jié)點(diǎn)

  • 本文實(shí)現(xiàn)的雙向鏈表結(jié)構(gòu)如下


    結(jié)點(diǎn)

1.4 雙向鏈表的基本操作

  • 本文主要實(shí)現(xiàn)了雙向鏈表的以下操作
    • 判斷是否為空
    • 獲取鏈表長(zhǎng)度
    • 在頭部插入元素
    • 在尾部插入元素
    • 刪除指定位置元素
    • 刪除指定值的元素
    • 查找是否包含指定值
    • 查找指定位置元素的值
    • 遍歷鏈表所有結(jié)點(diǎn)

1.5 雙向鏈表的初始化

//定義雙向鏈表結(jié)構(gòu)體

type DuLNode struct {
    data  interface{} //數(shù)據(jù)域
    prior *DuLNode    //指針域 -> 指向直接前驅(qū)
    next  *DuLNode    //指針域 -> 指向直接后繼
}

type DuList struct {
    length   int //儲(chǔ)存鏈表的長(zhǎng)度
    headNode *DuLNode
}

func InitDuList() *DuList {
    //即構(gòu)造一個(gè)空的雙向鏈表L(包含空的頭結(jié)點(diǎn))
    node := new(DuLNode)
    L := new(DuList)
    L.headNode = node
    return L
}

//這個(gè)非空判斷也可以判斷l(xiāng)ist.headNode.next == nil來完成
func (list *DuList) IsNull() bool {
    if list.length == 0 {
        return true
    } else {
        return false
    }
}

2、雙向鏈表的插入

  • 同樣，首先來實(shí)現(xiàn)雙向鏈表的插入操作

2.1、在指定位置插入元素

//雙向鏈表的插入(均為前插)
func (list *DuList) InsertElem(index int, v interface{}) {
    if index <= 0 || index > list.length {
        fmt.Println("err")
    } else {
        head := list.headNode
        fnode := head.next
        node := &DuLNode{data: v}
        if index == 1 { //處理向第一位插入
            node.next = head.next
            node.prior = head
            head.next = node
        } else {
            for count := 1; count < index; count++ {
                fnode = fnode.next
            }
            fnode.prior.next = node
            node.prior = fnode.prior
            node.next = fnode
        }
        list.length++
    }
}

2.2、在頭部插入元素

//從頭部添加元素
func (list *DuList) AddElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() { //處理空表的插入
        head.next = node
        node.prior = head
    } else {
        fnode := head.next
        head.next = node
        node.prior = head
        node.next = fnode
        fnode.prior = node
    }
    list.length++
    return
}

2.3、在尾部插入元素

//從尾部插入元素
func (list *DuList) AppendElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() {  //處理空表
        head.next = node
        node.prior = head
    } else {
        lnode := head.next
        for lnode.next != nil {
            lnode = lnode.next
        }
        lnode.next = node
        node.prior = lnode
    }
    list.length++
    return
}

3、雙向鏈表的刪除------總結(jié)go如何實(shí)現(xiàn)while

3.1、刪除指定值的元素

//按值移除元素
func (list *DuList) RemoveElem(v interface{}) {
    head := list.headNode
    fnode := head.next
    if fnode.data == v { //處理移除的元素是第一個(gè)
        fnode.next.prior = head
        head.next = fnode.next
        list.length--
        return
    } else {
        for fnode.next != nil { //處理中段
            if fnode.data == v {
                fnode.prior.next = fnode.next
                fnode.next.prior = fnode.prior
                list.length--
                return
            } else {
                fnode = fnode.next
            }
        }
        if fnode.next == nil && fnode.data == v {
           //處理最后一個(gè)元素，由于go語言不含while語句，且此時(shí)已經(jīng)到達(dá)鏈尾，需要對(duì)鏈尾元素做以此判斷
            fnode.prior.next = nil
            fnode.prior = nil
            list.length--
            return
        }
        fmt.Println("fail")
        return
    }
}

3.2 刪除指定位置的元素

//按位移除元素
func (list *DuList) DeleteElem(index int) {
    if index <= 0 || index > list.length {
        fmt.Println("刪除位置不合理")
        return
    } else {
        head := list.headNode
        fnode := head.next
        if index == 1 {
            fnode.next.prior = head
            head.next = fnode.next
        } else {
            for count := 0; count < index-1; count++ {
                fnode = fnode.next
            }
            if index == list.length { //處理最后一位元素，與刪除指定值遇到的問題相同
                fnode.prior.next = nil
                fnode.prior = nil
                list.length--
                return
            }
            fnode.prior.next = fnode.next
            fnode.next.prior = fnode.prior
        }
        list.length--
        return
    }
}

4、雙向鏈表的查詢

4.1、查詢是否包含指定值(按值查詢)

//雙向鏈表的按值查找
func (list *DuList) LocateElem(v interface{}) bool {
    if list.IsNull() {
        fmt.Println("err")
        return false
    } else {
        head := list.headNode
        fnode := head.next
        for fnode.next != nil {
            if fnode.data == v {
                return true
            }
            fnode = fnode.next
        }
        if fnode.data == v { //由于go語言不含while語句，且此時(shí)已經(jīng)到達(dá)鏈尾，需要對(duì)鏈尾元素做以此判斷
            return true
        }
        return false
    }
}

4.2、查詢指定位置的值

//雙向鏈表的取值
func (list *DuList) GetElem(index int) int {
    if index <= 0 || index > list.length {
        return 0
    } else {
        head := list.headNode
        fnode := head.next
        for j := 1; j < index; j++ {
            if fnode.next != nil {
                fnode = fnode.next
            }
        }
        return fnode.data.(int)
    }
}

4.3、遍歷雙向鏈表

func (list *DuList) ShowList() {
    if !list.IsNull() {
        cur := list.headNode.next
        for {
            fmt.Printf("\t%v", cur.data)
            if cur.next != nil {
                cur = cur.next
            } else {
                break
            }
        }
        fmt.Printf("\n")
    }
}

5、完整代碼及結(jié)果展示

package main

import "fmt"

//定義單鏈表結(jié)構(gòu)體

type DuLNode struct {
    data  interface{} //數(shù)據(jù)域
    prior *DuLNode    //指針域 -> 指向直接前驅(qū)
    next  *DuLNode    //指針域 -> 指向直接后繼
}

type DuList struct {
    length   int //儲(chǔ)存鏈表的長(zhǎng)度
    headNode *DuLNode
}

// type Method interface {
//  IsNull() bool                    //1、判斷是否為空
//  GetLength() int                  //2、獲取鏈表長(zhǎng)度
//  InsertElem(i int, v interface{}) //3、在指定位置添加元素
//  AddElem(v interface{})           //4、在頭部插入元素
//  AppendElem(v interface{})        //5、在尾部插入元素
//  DeleteElem(i int)                //6、刪除指定位置元素
//  RemoveElem(v interface{})        //7、刪除指定值的元素
//  ContaineElem(v interface{}) bool //8、是否包含指定值的元素
//  LocateElem(i int) interface{}    //9、查找指定位置元素的值
//  ShowList()                       //10、遍歷鏈表所有結(jié)點(diǎn)
// }
func InitDuList() *DuList {
    //即構(gòu)造一個(gè)空的雙向鏈表L(包含頭指針)
    node := new(DuLNode)
    L := new(DuList)
    L.headNode = node
    return L
}

//雙向鏈表的取值
func (list *DuList) GetElem(index int) int {
    if index <= 0 || index > list.length {
        return 0
    } else {
        head := list.headNode
        fnode := head.next
        for j := 1; j < index; j++ {
            if fnode.next != nil {
                fnode = fnode.next
            }
        }
        return fnode.data.(int)
    }
}

//雙向鏈表的按值查找
func (list *DuList) LocateElem(v interface{}) bool {
    if list.IsNull() {
        fmt.Println("err")
        return false
    } else {
        head := list.headNode
        fnode := head.next
        for fnode.next != nil {
            if fnode.data == v {
                return true
            }
            fnode = fnode.next
        }
        if fnode.data == v { //由于go語言不含while語句，且此時(shí)已經(jīng)到達(dá)鏈尾，需要對(duì)鏈尾元素做以此判斷
            return true
        }
        return false
    }
}

//雙向鏈表的插入(均為前插)
func (list *DuList) InsertElem(index int, v interface{}) {
    if index <= 0 || index > list.length {
        fmt.Println("err")
    } else {
        head := list.headNode
        fnode := head.next
        node := &DuLNode{data: v}
        if index == 1 { //處理向第一位插入
            node.next = head.next
            node.prior = head
            head.next = node
        } else {
            for count := 1; count < index; count++ {
                fnode = fnode.next
            }
            fnode.prior.next = node
            node.prior = fnode.prior
            node.next = fnode
        }
        list.length++
    }
}

//按位移除元素
func (list *DuList) DeleteElem(index int) {
    if index <= 0 || index > list.length {
        fmt.Println("刪除位置不合理")
        return
    } else {
        head := list.headNode
        fnode := head.next
        if index == 1 {
            fnode.next.prior = head
            head.next = fnode.next
        } else {
            for count := 0; count < index-1; count++ {
                fnode = fnode.next
            }
            if index == list.length { //處理最后一位元素
                fnode.prior.next = nil
                fnode.prior = nil
                list.length--
                return
            }
            fnode.prior.next = fnode.next
            fnode.next.prior = fnode.prior
        }
        list.length--
        return
    }
}

//按值移除元素
func (list *DuList) RemoveElem(v interface{}) {
    head := list.headNode
    fnode := head.next
    if fnode.data == v { //處理移除的元素是第一個(gè)
        fnode.next.prior = head
        head.next = fnode.next
        list.length--
        return
    } else {
        for fnode.next != nil { //處理中段
            if fnode.data == v {
                fnode.prior.next = fnode.next
                fnode.next.prior = fnode.prior
                list.length--
                return
            } else {
                fnode = fnode.next
            }
        }
        if fnode.next == nil && fnode.data == v { //處理最后一個(gè)元素，
由于go語言不含while語句，且此時(shí)已經(jīng)到達(dá)鏈尾，需要對(duì)鏈尾元素做以此判斷
            fnode.prior.next = nil
            fnode.prior = nil
            list.length--
            return
        }
        fmt.Println("fail")
        return
    }
}

//這個(gè)非空判斷也可以判斷l(xiāng)ist.headNode.next == nil
func (list *DuList) IsNull() bool {
    if list.length == 0 {
        return true
    } else {
        return false
    }
}

//從頭部添加元素
func (list *DuList) AddElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() { //處理空表的插入
        head.next = node
        node.prior = head
    } else {
        fnode := head.next
        head.next = node
        node.prior = head
        node.next = fnode
        fnode.prior = node
    }
    list.length++
    return
}

func (list *DuList) AppendElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() {
        head.next = node
        node.prior = head
    } else {
        lnode := head.next
        for lnode.next != nil {
            lnode = lnode.next
        }
        lnode.next = node
        node.prior = lnode
    }
    list.length++
    return
}

func (list *DuList) ShowList() {
    if !list.IsNull() {
        cur := list.headNode.next
        for {
            fmt.Printf("\t%v", cur.data)
            if cur.next != nil {
                cur = cur.next
            } else {
                break
            }
        }
        fmt.Printf("\n")
    }
}

func main() {
    L := InitDuList()
    msg := []int{12, 5, 3, 8, 55, 13}
    for i := range msg {
        L.AppendElem(msg[i])
    }
    L.ShowList()
    L.RemoveElem(13)
    L.ShowList()
    L.DeleteElem(5)
    L.ShowList()
    L.InsertElem(2, 10)
    L.ShowList()
    fmt.Println(L.LocateElem(8))
    fmt.Println(L.GetElem(5))
}

//結(jié)果展示
        12      5       3       8       55      13
        12      5       3       8       55
        12      5       3       8
        12      10      5       3       8
true
8

6、總結(jié)

  • 在實(shí)現(xiàn)單鏈表時(shí)沒有為鏈表設(shè)置一個(gè)空的頭結(jié)點(diǎn)，本次為其添加了一個(gè)空的頭結(jié)點(diǎn)，確實(shí)是會(huì)方便很多，對(duì)線性表有了更加清晰的了解。
  • go語言的循環(huán)語句只有if-else和for循環(huán)語句，導(dǎo)致在進(jìn)行迭代時(shí)無法對(duì)最后一位元素進(jìn)行操作，目前的解決辦法是在進(jìn)行最后一次循環(huán)結(jié)束后，再進(jìn)行一次單獨(dú)的判斷。在學(xué)習(xí)go的do-while循環(huán)后，更新博客。
  • 參考博客
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容