链表是一种线性表,单并非是顺序存储的;而是链表上的每一个节点都有指向其它节点的指针.链表有单向链表和双向链表之分; 单向链表的每个节点有数据域和指向下一节点的指针组成;
单向链表分为带头节点和不带头节点;不带头节点的链表在做插入/删除操作的时候需要做一些非空判断;
头节点和头指针
- 头节点:放了方便操作链表,放在第一个有效节点之前的节点;其next指针指向第一个有效节点
- 头指针:链表的第一个节点指针;若有头节点则指向头节点,否则指向第一个有效节点
- 链表可以没头节点,但不能无头指针;
定义节点和链表
// Node 链表节点type Node struct { value int next *Node}// List 单向链表type List struct { len int head *Node}复制代码 1.链表的初始化及清空
// New 新建链表func New() *List { return new(List).Reset()}// Reset 清空链表func (l *List) Reset() *List { l.len = 0 if l.head == nil { l.head = &Node{0, nil} } l.head.next = nil return l}复制代码 2.链表的基本情况操作
// Len 链表长度func (l *List) Len() int { return l.len}// IsEmpty 是否是空表func (l *List) IsEmpty() bool { return l.First() == nil}// First 链表的第一个有效节点func (l *List) First() *Node { return l.head.next}// Last 链表的最后一个节点,空表则返回nilfunc (l *List) Last() *Node { if la := l.last(); la != l.head { return la } return nil}// last 若为空表,则返回头节点,否则返回第一个有效节点(非nil)func (l *List) last() *Node { h := l.head for h != nil && h.next != nil { h = h.next } return h}复制代码 3.查找某个节点的前一个节点
// Before 节点at前一个节点func (l *List) Before(at *Node) *Node { b := l.before(at) if b == nil { // 不包含节点 return nil } if b == l.head { return nil } return b}// before 节点at前一个节点,若at为第一个有效节点,则返回头节点func (l *List) before(at *Node) *Node { if at == nil { return nil } h := l.head for h != nil && h.next != at { h = h.next } return h}复制代码 4.插入新元素,分为4中情况
- 4.1头插入插入元素
// InsertFront 头插法插入新元素func (l *List) InsertFront(v int) *Node { nn := l.insertValue(v, l.head) l.len++ return nn}复制代码 - 4.2尾插法插入新元素
// InsertLast 尾插法插入新元素func (l *List) InsertLast(v int) *Node { la := l.last() nn := l.insertValue(v, la) l.len++ return nn}复制代码 - 4.3在某一节点之前插入新元素
func (l *List) InsertBefore(v int, at *Node) *Node { b := l.before(at) if b == nil { // 不包含节点 return nil } nn := l.insertValue(v, b) l.len++ return nn}复制代码 - 4.4在某一节点之后插入新元素
func (l *List) InsertAfter(v int, at *Node) *Node { nn := l.insertValue(v, at) l.len++ return nn}复制代码 - 这是两个插入元素的辅助方法
// insert 在at节点后面插入节点nfunc (l *List) insert(n, at *Node) *Node { nn := at.next n.next = nn at.next = n return n}// insertValue 在at节点后面插入新元素vfunc (l *List) insertValue(v int, at *Node) *Node { nn := &Node{v, nil} l.insert(nn, at) return nn}复制代码 5.删除某一节点
func (l *List) Delete(n *Node) int { f := l.before(n) if f == nil { // 不包含节点 return n.value } f.next = n.next n.next = nil l.len-- return n.value}复制代码 6.移动节点,分为两种情况
- 6.1 移动节点A到节点B之后
func (l *List) MoveAfter(source, dest *Node) *Node { if source == nil || dest == nil { return source } bs := l.before(source) ds := l.before(dest) if bs == nil || ds == nil { // 不包含节点 return source } bs.next = source.next source.next = dest.next dest.next = source return source}复制代码 - 6.2 移动节点A到节点B之前
func (l *List) MoveBefore(source, dest *Node) *Node { if source == nil || dest == nil { return source } bs := l.before(source) ds := l.before(dest) if bs == nil || ds == nil { // 不包含节点 return source } bs.next = source.next source.next = dest ds.next = source return source}复制代码 7.反转链表
func (l *List) Reversed() *List { if l.IsEmpty() { return l } pre := (*Node)(nil) n := l.First() for n != nil { nn := n.next n.next = pre if nn == nil { l.head.next = n break } pre = n n = nn } return l}复制代码 这里详细说明下反转链表的步骤
链表原型: head-->A-->B-->C-->D-->nil
- 1:链表为空,直接返回
- 2:链表非空,比如操作C, 取出当前节点C
- 3:取出下一节点D; d==c.next
- 4:判断D是否为nil,为nil设置头节点的next = c ,结束循环
- 5:D不为nil,C.next = pre(前一节点)
- 6:重新赋值pre为当前节点: pre= C
- 7:把当前节点n设为D: n=d
注意代码中的pre定义
pre := (*Node)(nil)复制代码
这里，因为有头节点的存在,我们可以在反转的时候把头节点想象成nil
8.最后来一个方便查看链表分布的方法
// 空表: "nil"// 非空: "1-->2-->3-->nil"func (l *List) Str() string { if l.len == 0 { return "nil" } var b strings.Builder for r := l.head.next; r != nil; { vs := strconv.FormatInt(int64(r.value), 10) b.WriteString(vs) b.WriteString("-->") r = r.next } b.WriteString("nil") return b.String()}复制代码