单链表

链表的特点

头插速度快
尾部查入要遍历到最后
链表适用于频繁到删除和插入，查询少不需要知道长度，遍历到nil 跳出
数组适用于频繁到查找，删除和插入比较少，要知道长度
进程列表双链表

单链表实现

代码编写记忆:

head 元素 value 一直为nil 即 list.head.pNext 才为第一个节点

单链表示意图

节点

 1package singlylinkedlist
 2
 3type SingleLinkNode struct {
 4	value interface{}
 5	pNext *SingleLinkNode
 6}
 7
 8//构造一个节点
 9func NewSingleLinkNode(data interface{}) *SingleLinkNode {
10	var node = new(SingleLinkNode)
11	node.value = data
12	return node
13}
14
15// 返回值
16func (node *SingleLinkNode) Value() interface{} {
17	return node.value
18}
19
20// 返回下一个节点
21func (node *SingleLinkNode) Pnext() *SingleLinkNode {
22	return node.pNext
23}

单链表实现

  1package singlylinkedlist
  2
  3import (
  4	"fmt"
  5)
  6
  7type SingleLink interface {
  8	GetFirstNode() *SingleLinkNode        //获取头节点
  9	InsertNodeFront(node *SingleLinkNode) //头部插入
 10	InsertNodeBack(node *SingleLinkNode)  // 尾部插入
 11	//在一个节点之后插入
 12	InsertNodeValueBack(dest interface{}, node *SingleLinkNode) bool
 13	//在一个节点之前插入
 14	InsertNodeValueFront(dest interface{}, node *SingleLinkNode) bool
 15	//根据索引抓取指定位置的节点
 16	GetNodeAtIndex(index int) *SingleLinkNode
 17	// 删除一个节点
 18	DeleteNode(dest *SingleLinkNode) bool
 19	//删除指定位置的节点
 20	DeleteAtIndex(index int) bool
 21	String() string // //返回链表字符串
 22}
 23
 24type SingLinkList struct {
 25	head   *SingleLinkNode
 26	length int // 链表的长度
 27}
 28
 29//创建链表
 30
 31func NewSingLinkList() *SingLinkList {
 32	head := NewSingleLinkNode(nil)
 33	return &SingLinkList{head: head, length: 0}
 34}
 35
 36// 第一个元素
 37func (list *SingLinkList) GetFirstNode() *SingleLinkNode {
 38	return list.head.pNext
 39}
 40
 41//头部插入
 42func (list *SingLinkList) InsertNodeFront(node *SingleLinkNode) {
 43	// 如果没有头元素
 44	if list.head == nil {
 45		list.head.pNext = node
 46		node.pNext = nil
 47	} else {
 48		bak := list.head
 49		node.pNext = bak.pNext
 50		list.head.pNext = node
 51	}
 52	list.length++
 53}
 54
 55//尾部插入
 56func (list *SingLinkList) InsertNodeBack(node *SingleLinkNode) {
 57	if list.head == nil {
 58		list.head.pNext = node
 59		node.pNext = nil
 60	} else {
 61		bak := list.head
 62		for bak.pNext != nil {
 63			bak = bak.pNext
 64		}
 65		bak.pNext = node
 66	}
 67	list.length++
 68}
 69
 70//节点值 前追加
 71func (list *SingLinkList) InsertNodeValueFront(dest interface{}, node *SingleLinkNode) bool {
 72	var isFind = false
 73	bak := list.head
 74	for bak.pNext != nil {
 75		if bak.pNext.value == dest {
 76			isFind = true
 77			break
 78		}
 79		bak = bak.pNext
 80	}
 81	if isFind {
 82		node.pNext = bak.pNext
 83		bak.pNext = node
 84		list.length++
 85	}
 86
 87	return isFind
 88}
 89
 90//节点值 后追加
 91func (list *SingLinkList) InsertNodeValueBack(dest interface{}, node *SingleLinkNode) bool {
 92	var isFind = false
 93	bak := list.head
 94	for bak.pNext != nil {
 95		if bak.value == dest {
 96			isFind = true
 97			break
 98		}
 99		bak = bak.pNext
100	}
101	if isFind {
102		node.pNext = bak.pNext
103		bak.pNext = node
104		list.length++
105	}
106
107	return isFind
108}
109
110//获得指定位置的节点 从0开始-》lenth-1  .
111func (list *SingLinkList) GetNodeAtIndex(index int) *SingleLinkNode {
112	if index > list.length-1 || index < 0 {
113		return nil
114	}
115	/*
116		phead:=list.head
117		for index >-1{
118			phead=phead.pNext //向后循环
119			index-- //向后循环过程
120		}
121		return phead
122	*/
123	var i int
124	node := list.head
125	for node.pNext != nil {
126		node = node.pNext
127		if index == i {
128			//break
129			return node
130		}
131		i++
132	}
133	return node
134}
135
136//删除节点
137func (list *SingLinkList) DeleteNode(dest *SingleLinkNode) bool {
138	if dest == nil {
139		return false
140	}
141	node := list.head
142	for node.pNext != nil {
143		if node.pNext == dest {
144			node.pNext = node.pNext.pNext
145			list.length--
146			return true
147		}
148		node = node.pNext
149	}
150	return false
151}
152
153//删除指定位置的节点
154func (list *SingLinkList) DeleteAtIndex(index int) bool {
155	if index > list.length-1 || index < 0 {
156		return false
157	}
158	var i int
159	node := list.head
160	for node.pNext != nil {
161		if index == i {
162			node.pNext = node.pNext.pNext
163			return true
164		}
165		node = node.pNext
166		i++
167	}
168	return false
169}
170
171//打印链表
172func (list *SingLinkList) String() string {
173	var listString string
174	node := list.head //头部节点
175	for node.pNext != nil {
176		listString += fmt.Sprintf("%v-->", node.pNext.value)
177		node = node.pNext //循环
178	}
179	listString += fmt.Sprintf("nil")
180	return listString //打印链表字符串
181}
182
183
184
185//获得中间节点
186func (list *SingLinkList) GetMid() *SingleLinkNode {
187	node := list.head //头部节点
188	if node == nil {
189		return nil
190	}
191	phead1 := list.head
192	phead2 := list.head
193	for phead2 != nil && phead2.pNext != nil {
194		phead1 = phead1.pNext
195		phead2 = phead2.pNext.pNext
196	}
197	return phead1
198}
199
200// 链表反转
201// 下一个节点 指向 前一个节点, 头节点指向 原来的最后一个节点
202func (list *SingLinkList) ReverseList() {
203	if list.head == nil || list.head.pNext == nil {
204		return //链表为空或者链表只有一个节点
205	} else {
206		var pre *SingleLinkNode                   //前面节点
207		var cur *SingleLinkNode = list.head.pNext //当前节点
208		for cur != nil {
209			curNext := cur.pNext // 后续节点
210			cur.pNext = pre      //反转第一步
211
212			pre = cur     //持续推进
213			cur = curNext //持续推进
214		}
215		// fmt.Println(pre)
216		// list.head.pNext.pNext=nil
217		list.head.pNext = pre
218	}
219}
220
221
222/*
223
2241 -> 2-》3-》4-》5->nil                            2
225  curNext   2-》3-》4-》5->nil                    3-》4-》5->nil 
226cur: 1->nil                                     cur 2->1->nil
227pre =  1->nil                                   pre  2->1->nil     ...      5->4->3->2->1->nil
228cur =   2-》3-》4-》5->nil                       3-》4-》5->nil     
229*/

单链表测试

 1package singlylinkedlist
 2
 3import (
 4	"github.com/stretchr/testify/assert"
 5	"testing"
 6)
 7
 8func TestArrayList(t *testing.T) {
 9	node1 := NewSingleLinkNode(1)
10	node2 := NewSingleLinkNode(2)
11	node3 := NewSingleLinkNode(3)
12	node4 := NewSingleLinkNode(4)
13	node5 := NewSingleLinkNode(5)
14	node6 := NewSingleLinkNode(6)
15	node10 := NewSingleLinkNode(10)
16	link := NewSingLinkList()
17	t.Log(link.String())
18	link.InsertNodeFront(node1)
19	t.Log(link.String())
20	link.InsertNodeFront(node2)
21	t.Log(link.String())
22	link.InsertNodeFront(node3)
23	t.Log(link.String())
24	t.Log("中间节点：", (link.GetMid().Value()))
25	link.InsertNodeBack(node10)
26	t.Log(link.String())
27	t.Log(link.GetFirstNode().Value())
28	link.InsertNodeValueBack(3, node4)
29	t.Log(link.String())
30	link.InsertNodeValueFront(2, node5)
31	t.Log(link.String())
32	t.Log("中间节点：", (link.GetMid().Value()))
33	link.InsertNodeValueFront(3, node6)
34	t.Log(link.String())
35
36	firstNode := link.GetNodeAtIndex(0)
37	assert.Equal(t, firstNode.Value(), 6, "根据索引获得节点失败")
38	twoNode := link.GetNodeAtIndex(1)
39	assert.Equal(t, twoNode.Value(), 3, "根据索引获得节点失败")
40	//链表反转
41	link.ReverseList()
42	t.Log(link.String())
43	link.DeleteAtIndex(0)
44	t.Log(link.String())
45	link.DeleteAtIndex(3)
46	t.Log(link.String())
47	link.DeleteNode(node10)
48	t.Log(link.String())
49	link.DeleteNode(node4)
50	t.Log(link.String())
51
52}

结果

 1=== RUN   TestArrayList
 2--- PASS: TestArrayList (0.00s)
 3    singleLink_test.go:17: nil
 4    singleLink_test.go:19: 1-->nil
 5    singleLink_test.go:21: 2-->1-->nil
 6    singleLink_test.go:23: 3-->2-->1-->nil
 7    singleLink_test.go:24: 中间节点： 2
 8    singleLink_test.go:26: 3-->2-->1-->10-->nil
 9    singleLink_test.go:27: 3
10    singleLink_test.go:29: 3-->4-->2-->1-->10-->nil
11    singleLink_test.go:31: 3-->4-->5-->2-->1-->10-->nil
12    singleLink_test.go:32: 中间节点： 5
13    singleLink_test.go:34: 6-->3-->4-->5-->2-->1-->10-->nil
14    singleLink_test.go:41: 链表反转
15    singleLink_test.go:43: 10-->1-->2-->5-->4-->3-->6-->nil
16    singleLink_test.go:45: 1-->2-->5-->4-->3-->6-->nil
17    singleLink_test.go:47: 1-->2-->5-->3-->6-->nil
18    singleLink_test.go:49: 1-->2-->5-->3-->6-->nil
19    singleLink_test.go:51: 1-->2-->5-->3-->6-->nil
20PASS
21ok      datastruct/list/singlylinkedlist        0.014s

郝林 Go语言核心36讲第8讲

链表的特点

单链表实现

单链表测试

版权