【算法笔记】链表(Linked List)的简单实践

今天用go语言简单的写了一下单向链表的方法。
为了以后方便查看，当做笔记整理了一下~~

1.链表(Linked List)

维基百科里是这么解释的。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，
但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，
但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

看看下图:

图片备用地址

linked_list

简单的说就是把数据链接起来保存的数据结构。
因为需要链接，所以每个节点都需要存储下一个节点的信息。
这一特性是链表的插入和删除比较快。查询慢(因为只记录下一个节点，想找特定的值只能全部遍历)。
但是数组就恰恰相反，查询很快，插入和删除的效率就不高了。
可以看看下图：

链表的插入

只要把3和7的中间加入5就行了。

图片备用地址

linked_list

链表的删除

这就更简单了，直接把3连接到7就行了。

图片备用地址

linked_list

数组的插入

先把7和9各向右挪一格，然后把5放进去。如果是个很长的数组，这效率就可想而知了。

图片备用地址

linked_list

数组的删除

这也是先吧5删除后，再把7和9挪到左边。

图片备用地址

linked_list

这里简单的说明一下，二叉树就是有链表的插入和删除的高效率，而且又有不慢的查询速度的数组和链表相结合的数据结构。

2.链表的结构

链表有好几种结构，但是比较常有的有3种。
单向链表，双向链表，循环链表。

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
看下图应该很容易理解。

图片备用地址

linked_list

双向链表

每个节点有两个连接：一个指向前一个节点，而另一个指向下一个节点。

图片备用地址

linked_list

循环链表

首节点和末节点被连接在一起。形成一个循环。

图片备用地址

linked_list

3.单向链表的实例

struct

//链表
type LinkedList struct {
    Head *ListNode  //头部节点
    Tail *ListNode  //尾部节点
    Size int        //链表长度
}

//节点
type ListNode struct {
    Value int   //节点的值
    Next  *ListNode //下一个节点
}

Insert

//position: 要插入的位置
//number: 要插入的值
func (node *LinkedList) Insert(position int, number int) {
    if position > node.Size {
        return
    }

    newNode := &ListNode{Value: number}

    if position == 0 {
        newNode.Next = node.Head
        node.Head = newNode
        if node.Tail == nil {
            node.Tail = newNode
        }
    } else if position == node.Size {
        node.Tail.Next = newNode
        node.Tail = newNode
    } else {
        currentNode := node.Head
        for i := 0; i < position; i++ {
            currentNode = currentNode.Next
        }

        newNode.Next = currentNode.Next
        currentNode.Next = newNode
    }
    node.Size++
}

Delete

//number: 需要删除的值
func (node *LinkedList) Delete(number int) {
    if node.Head == nil || node.Tail == nil {
        return
    }

    if node.Head.Value == number {
        node.Head = node.Head.Next
        node.Size--
        if node.Size == 0 {
            node.Tail = node.Head
        }
        return
    }

    preNode := node.Head
    curNode := node.Head
    for i := 0; i < node.Size; i++ {
        if curNode.Value == number {
            if curNode == node.Tail {
                node.Tail = preNode
            }
            preNode.Next = curNode.Next
            node.Size--
            return
        }
        preNode = curNode
        curNode = curNode.Next
    }
}

Update

func (node *LinkedList) Update(old_number int, new_number int) int {
    currentNode := node.Head
    for i := 0; i < node.Size; i++ {
        if currentNode.Value == old_number {
            currentNode.Value = new_number
            return i
        }
        currentNode = currentNode.Next
    }
    return -1
}

Search

func (node *LinkedList) Search(number int) int {
    currentNode := node.Head
    for i := 0; i < node.Size; i++ {
        if currentNode.Value == number {
            return i
        }
        currentNode = currentNode.Next
    }
    return -1
}

Print

func (node *ListNode) Print() {
    if node == nil || node.Value == 0 {
        return
    } else {
        fmt.Print(node.Value, " ")
        node.Next.Print()
    }
}

执行结果

func main() {
    var linkedlist LinkedList
    linkedlist.Insert(0, 1)
    linkedlist.Insert(1, 2)
    linkedlist.Insert(2, 3)
    linkedlist.Insert(3, 4)
    linkedlist.Insert(4, 5)
    linkedlist.Insert(5, 6)
    linkedlist.Insert(6, 7)
    linkedlist.Insert(7, 8)
    fmt.Println("----insert 1,2,3,4,5,6,7,8----")
    linkedlist.Head.Print()
    fmt.Println("")
    fmt.Println("------update 5 => 55 ------")
    linkedlist.Update(5, 55)
    linkedlist.Head.Print()
    fmt.Println("")
    fmt.Println("-------- delete 55 --------")
    linkedlist.Delete(55)
    linkedlist.Head.Print()
    fmt.Println("")
    fmt.Println("-------- delete 9 --------")
    linkedlist.Delete(9)
    linkedlist.Head.Print()
    fmt.Println("")
    fmt.Println("-------- search 4  --------")
    fmt.Println("index:", linkedlist.Search(4))
}

执行结果为：

$ go run main.go
----insert 1,2,3,4,5,6,7,8----
1 2 3 4 5 6 7 8 
------update 5 => 55 ------
1 2 3 4 55 6 7 8
-------- delete 55 --------
1 2 3 4 6 7 8
-------- delete 9 --------
1 2 3 4 6 7 8
-------- search 4  --------
index: 3

---

后续

今天我看资料有个面试题是反转单项链表，我以为会很简单，结果写了半小时...^^;;
有几个坑大家需要注意一下...

struct

//链表
type LinkedList struct {
    Head *ListNode  //头部节点
    Tail *ListNode  //尾部节点
    Size int        //链表长度
}

//节点
type ListNode struct {
    Value int   //节点的值
    Next  *ListNode //下一个节点
}

反转链表方法

我们先看看错误的写法

func (l *LinkList) ReverseLinkedList() {
    if l == nil || l.Head == nil {
        return
    }
    node := Node{Value: l.Head.Value}
    curNode := l.Head
    for curNode.Next != nil {
        newNode := Node{Value: curNode.Value}
        newNode.Next = &node
        node = newNode
        curNode = curNode.Next
    }
    l.Head = &node
}

再看看正确的写法

func (l *LinkList) ReverseLinkedList() {
    if l == nil || l.Head == nil {
        return
    }
    node := Node{}
    curNode := l.Head
    for curNode != nil {
        newNode := node 
        node.Value = curNode.Value
        node.Next = &newNode
        curNode = curNode.Next
    }
    l.Head = &node
}

原因其实很简单，我们习惯性的赋值只会修改指针指向的地方，后续的操作就可想而知了。

执行结果

func (node *Node) Print() {
    if node == nil || node.Value == 0 {
        return
    } else {
        fmt.Print(node.Value, " ")
        node.Next.Print()
    }
}

func main() {
    linkList := LinkList{}
    linkList.Head = &Node{Value: 1}
    linkList.Head.Next = &Node{Value: 2}
    linkList.Head.Next.Next = &Node{Value: 3}
    linkList.Head.Next.Next.Next = &Node{Value: 4}

    linkList.ReverseLinkedList()

    linkList.Head.Print()
}

执行结果为：

$ go run main.go
4 3 2 1 

约瑟夫问题

struct

type CircleLinkedList struct {
    Head *ListNode
    Tail *ListNode
    Size int
}

方法

func (c *CircleLinkedList) JosephusCircleLinkedList(startNo, count, sum int) {
    for i := 1; i < startNo; i++ {
        c.Head = c.Head.Next
        c.Tail = c.Tail.Next
    }

    for {
        if c.Head == c.Tail {
            break
        }
        for i := 0; i < count-1; i++ {
            c.Head = c.Head.Next
            c.Tail = c.Tail.Next
        }
        fmt.Printf("出队元素：%d\n", c.Head.Value)
        c.Head = c.Head.Next
        c.Tail.Next = c.Head

    }
    fmt.Printf("最后剩下的元素是：%d", c.Head.Value)
}

执行结果

func main() {
    c := CircleLinkedList{}
    c.Head = &ListNode{Value: 1}
    c.Head.Next = &ListNode{Value: 2}
    c.Head.Next.Next = &ListNode{Value: 3}
    c.Head.Next.Next.Next = &ListNode{Value: 4}
    c.Head.Next.Next.Next.Next = &ListNode{Value: 5}
    c.Tail = c.Head.Next.Next.Next.Next
    c.Tail.Next = c.Head
    c.Size = 5
    c.JosephusCircleLinkedList(1, 2, 5)
}

执行结果为：

$ go run main.go
出队元素：3
出队元素：5
出队元素：2
出队元素：1
最后剩下的元素是：4

---

欢迎大家的意见和交流

email: li_mingxie@163.com