链表都是由许多相同类型的数据按照特定的顺序排列的线性表。各数据项在内存中是不连续且随机的，其优点是删除和新增都很方便，但是缺点也很明显，无法想数组那样可以随机读取数据，只能按顺序进行查找。

0x01 单向链表

一个单向链表基本是由两个元素所组成，而指针将会指向下一个元素的位置。
在单向链表中，第一个节点就是链表头指针，而最后一个节点指向的是None，表示他是链表尾。
例如链表A={a,b,c,d,x}

链表头指针显得相当重要。

1 建立单向链表

建立步骤

• 动态分配内存空间给新节点使用
• 将原链表尾部的指针next指向新元素所在的内存地址
• 将ptr指针指向新节点的内存位置，表示这是新的链表尾部
• 由于新的节点为当前链表的最后一个元素，因此将他的指针指向NULL
  代码示例

type Item struct{
	Data string
	Next *Item
}


func main(){
	head :=new(Item) //建立链表头部
	//保存头指针的位置
	head.Next=nil //当前无下一个元素
	ptr := head  //获取指针的位置
	//新增一个
	newData := new(Item)
	newData.Data="first"
	newData.Next=nil //下一个元素的NExt先设为nil
	ptr.Next = newData
    ptr = ptr.Next
}

2 遍历单向链表

遍历traverse的过程就是使用指针运算来访问链表中的每个节点。指针一开始指向链表的头部，每次读完链表的一个节点，就将ptr往下一个节点移动，知道ptr为null为止。

代码示例

package main

import "fmt"

type Item struct{
	Data string
	Next *Item
}


func main(){
	head :=new(Item)
	//保存头指针的位置
	head.Next=nil
	ptr := head
	var action int
	for{
		fmt.Print("(1)add (2)leave: ")
		fmt.Scanf("%d",&action)
		if action==1{
			//新增
			var value string
			fmt.Print("add value:")
			fmt.Scanf("%s",&value)
			newData := new(Item)
			newData.Data = value
			newData.Next = nil
			ptr.Next = newData
			ptr = ptr.Next  //或者ptr = newData
		}else{
			break
		}
	}
	println("start traverse....")
	//重置指针为表开头的位置
	ptr = head.Next
	for{
		if ptr.Next==nil{
			println(ptr.Data)
			break
		}
		println(ptr.Data)
		ptr = ptr.Next
	}
}

执行结果如下

(1)add (2)leave: 1
add value:first
(1)add (2)leave: 1
add value:second
(1)add (2)leave: 1
add value:third
(1)add (2)leave: 1
add value:fourth
(1)add (2)leave: 2
start traverse....
first
second
third
fourth

3 在单向链表中插入新的节点

从头部插入

新节点插入第一个借点前，成为链表的首节点， 只需要把新节点的指针指向链表原来的第一个节点，再把链表的头指针指向新节点就行了。

从中间插入

将新节点插入链表中间的位置，例如插入的节点在X与Y之间，只要将X节点的指针指向新节点，新节点的指针指向Y节点即可。

从尾部插入

新节点插入最后一个节点之后，只需要将最后一个节点的指针指向新节点， 新节点的指针再指向None即可。
删除节点与插入节点类似

插入代码示例

package main

import "fmt"

type Item struct{
	Data string
	Next *Item
}


func HeadInsert(head *Item, value string){
	newData := new(Item)
	newData.Data = value
	newData.Next = head.Next
	head.Next =  newData
}
func EndInsert(ptr *Item, value string){
	for{
		if ptr.Next==nil{
			newData := new(Item)
			newData.Data = value
			newData.Next = nil
			ptr.Next =  newData
			return
		}
		ptr=ptr.Next
	}

}
func MiddleInsert(ptr *Item, value,newValue string){
	for{
		if ptr.Next==nil{
			newData := new(Item)
			newData.Data = value
			newData.Next = nil
			ptr.Next =  newData
			return
		}
		if ptr.Data==value{
			//插入旧值的后面
			newData := new(Item)
			newData.Data = newValue
			newData.Next = ptr.Next
			ptr.Next =  newData
			return
		}
		ptr=ptr.Next

	}
}

func main(){
	head :=new(Item)
	//保存头指针的位置
	head.Next=nil
	ptr := head
	var action int
	var position int
	for{
		fmt.Print("(1)add (2)leave: ")
		fmt.Scanf("%d",&action)
		if action==1{
			//新增
			var value string
			var data  string
			fmt.Print("插入位置,(1) start (2)middle (3)end :")
			fmt.Scanf("%d",&position)
			if position==2{
				fmt.Print("插入到什么值后面:") //增加的值的前面一个值是什么
				fmt.Scanf("%s",&data)
			}
			fmt.Print("新值:")
			fmt.Scanf("%s",&value)
			//插入值
			//ptr复位
			ptr = head
			if position==1{
				HeadInsert(ptr,value)
			}else if position==2{
				MiddleInsert(ptr,data,value)
			}else{
				EndInsert(ptr,value)
			}

		}else{
			break
		}
	}
	println("start traverse....")
	//重置指针为表开头的位置
	ptr = head.Next
	for{
		if ptr.Next==nil{
			println(ptr.Data)
			break
		}
		println(ptr.Data)
		ptr = ptr.Next
	}
}

4单向链表的反转

如果要将单向链表反转，需要使用三个指针变量。

func Invert(head *Item){
	p := head  //p指向链表的开头
	var q *Item  //q是p的前一个节点
	for{
		if p==nil{
			break
		}
		r := q  //将r接到q后面
		q=p //将q接到p后面
		p = p.Next  //p移动到下一个节点
		q.Next= r  //q连接到之前的节点
	}
	//遍历
	for{
		if q.Next==nil{
			println(q.Data)
			break
		}
		println(q.Data)
		q = q.Next
	}

}

0x02 环形链表

在单向链表中，维持链表头指针是相当重要的事情， 因为单向链表具有方向性， 所有如果链表头指针被破坏或者遗失，整个链表就会遗失，并且浪费了整个链表的空间。
如果我们将链表的最后一个节点的指针指向链表头部，而不是指向nil，那么整个链表就成为了一个单方向的环形结构了。我们可以从任何一个节点遍历其他节点

代码示例

package main

import "fmt"

type Item struct{
	Data string
	Next *Item
}


func main(){
	head := new(Item)
	ptr := head
	ptr.Next = nil //目前无下一个元素
	var _select int
	for{
		print("(1) 新增 (2)离开:")
		fmt.Scanf("%d",&_select)
		if _select==2{
			break
		}
		var value string
		print("输入新值:")
		fmt.Scanf("%s",&value)
		newData := new(Item)
		newData.Data = value
		ptr.Next = newData
		newData.Next = nil  //先设置为空
		ptr = newData //存储指针为新元素地址
	}
	//完事了指向头部
	ptr.Next = head
	println()
	//遍历
	print("遍历")
	ptr = head
	for{
		println(ptr.Data)
		if ptr.Next == head{
			break
		}
		ptr = ptr.Next
	}
}

**遍历环形链表时与单向链表相似，只不过检查的条件变为ptr.Next==head
**

1 插入新节点

分为两种情况

• 将新节点插在第一个节点前成为链表头部：首先将新节点X的指针指向原链表头节点，并遍历整个链表找到链表末尾， 将它的指针指向新增的节点，最后将链表表头指针指向新的节点
  
• 将新节点X插在链表中的任意节点I之后：首先将新节点X的指针指向I节点的下一个节点，并将I节点的指针指向X节点。与单向链表相似
  

0x03 双向链表

单向链表和环形链表都是属于拥有方向性的链表，只能单向遍历。
我们可以将两个方向不同的链表结合起来，除了存放数据字段外，还有两个指针变量，其中一个指针指向后面的节点，另一个则指向前面的节点，这样的链表被称为双向链表。
优点： 查询效率高，执行速度较快，如果任一节点链接断裂，可经由反方向链表进行遍历，从而快速地重建完整的链表
缺点：由于双向链表有两个链接，因此在加入或者删除的时候都需要化更多的时间来调整指针，由于需要存储两个指针变量，所以较浪费空间。

1 链表的建立与遍历

对于双向链表的每一个节点而言，具有三个字段，中间的为数据字段，左右隔一个链接指针。双向链表可是是环形的也可以不是环形的，为了使用方便，通常加上一个链表头指针，他的数据字段不存放任何数据，其左指针指向链表的最后一个节点，而右指针指向第一个节点。
示例代码如下

package main

import "fmt"

type Item struct{
	LLink *Item
	Data string
	RLink *Item
}

func main(){
	//创建空的头指针
	head := &Item{
		LLink: nil,
		Data:  "",
		RLink: nil,
	}
	ptr := head
	for{
		print("(1) add  (2) leave:")
		var _select int
		fmt.Scanf("%d",&_select)
		if _select==2{
			break
		}
		//添加元素
		print("新增元素:")
		var element string
		fmt.Scanf("%s", &element)
		newData := new(Item)
		newData.Data = element
		ptr.RLink = newData
		ptr.LLink = ptr
		newData.RLink = nil
		ptr = newData
	}
	//遍历
	println("遍历")
	ptr = head.RLink
	for{
		println(ptr.Data)
		if ptr.RLink==nil{
			break
		}
		ptr = ptr.RLink
	}
}

双向链表的遍历相当灵活，如果往右开始遍历就类似于单向链表。向左遍历节点，则可以将上面的代码改成环形的双向链表，将头结点的LLink指向尾部， 尾部的RLink指向头部（这个操作可以在for循环外操作）

ptr.RLink = head
head.Link = ptr

2 节点修改

1 插入新节点

有3中可能

• 将新节点加入双向链表的第一个节点之前：将新节点的右指针rlink指向原链表的第一个节点，接着将源链表的第一个节点的左指针llink指向新节点，将原链表的链表头指向新的节点。

X.RLink = head
head.LLink = X
head=X

• 将新节点加入双向链表的末尾：将原链表的最后一个节点的右指针指向新节点，将新节点的左指针指向原链表的最后一个节点，并将新节点的右指针指向nil。

ptr.RLink=X
X.RLink = nil
X.LLink=ptr

• 将新节点加入链表中的ptr节点之后：首先将ptr节点的右指针指向新节点，再将新节点的左指针指向ptr节点， 接着将ptr节点的下一个节点的左指针指向新的节点，最后将新节点的右指针指向ptr的县一个节点

ptr.RLink.LLink=X
X.RLink = ptr.RLink
X.LLink = ptr
ptr.RLink=X