1 单链表的定义
代码仓库
https://gitee.com/babyb/data_srtuct
引用百度百科:
https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8/3228368?fr=aladdin
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
image.png
2 实现的功能
1 判断链表是否为空
2 单链表的长度
3 从头部加入单元素
4 尾部加入元素
5 指定位置元素
6 删除指定元素
7 删除指定位置的元素
8 查看是否包含某个元素
9 遍历/展示所有元素
数据结构定义
type Object interface {}
type Node struct{
Data Object //数据域
Next *Node //定义地址域 ( 指向下一个表的地址)
}
type List struct{
headNode *Node //头结点
}
3 每一个方法
3.1 判断链表是否为空
func (this *List) IsEmpty() bool{
if this.headNode == nil{
return true
}else{
return false
}
}
3.2获取链表长度
func (this *List) Length() int{
// 第一步, 获取链表的头结点
cur := this.headNode;
//定义一个计数器
count := 0;
for cur != nil{
count ++
cur = cur.Next
}
return count
}
3.3从链表头部添加元素
func (this *List) Add(data Object) *Node{
node := &Node{ Data: data}
node.Next = this.headNode
this.headNode = node;
return node;
}
3.4 链表尾部添加元素
func (this *List) Append(data Object){
node := &Node{Data: data}
if this.IsEmpty(){
//如果是空链表, 直接将该元素作为头结点
this.headNode = node
}else{
cur := this.headNode
//定义变量用于存储头结点
for cur.Next != nil{
cur = cur.Next
}
cur.Next = node
}
}
3.5链表指定位置添加元素
func (this *List) Insert(index int, data Object){
if index <0{
//在链表头部添加元素
this.Add(data)
}else if index > this.Length(){
this.Append(data)
}else{
pre :=this.headNode
count := 0;
//先查找到指定位置的前一个元素
for count < (index - 1) {
pre = pre.Next
count++
}
// 创建新结点
node := &Node{Data: data}
node.Next = pre.Next;
pre.Next = node
}
}
3.6删除链表指定值的元素
func (this *List) Remove( data Object){
pre := this.headNode
if pre.Data == data{
// 删除头部元素
this.headNode = pre.Next
}else{
for pre.Next != nil{
if pre.Next.Data == data{
//找到了指定元素, pre.Next 指向更靠后的那个元素
pre.Next = pre.Next.Next
}else{
// 如果没找到指定元素
pre = pre.Next
}
}
}
}
3.7 删除链表指定下标的元素
func (this *List) RemoveByIndex(index int){
pre := this.headNode
if index <= 0{
//移除头结点
this.headNode = pre.Next
}else if index > this.Length(){
fmt.Println("超出链表长度")
return
}else{
//
count := 0;
for count != (index -1) && pre.Next != nil{
count ++
pre = pre.Next
}
pre.Next = pre.Next.Next
}
}
3.8查看链表是否包含某个元素
func (this *List) Contain(data Object) bool {
cur := this.headNode
for cur != nil{
if cur.Data == data {
return true
}
cur = cur.Next
}
return false
}
3.9 遍历所有结点
func (this *List) ShowList(){
if !this.IsEmpty(){
cur := this.headNode
for cur != nil{
fmt.Printf("\t %v", cur.Data)
cur = cur.Next
}
}
}
3.10 占位符说明
fmt 中各种占位符, 参考下面这篇文章
https://studygolang.com/articles/2644
4 测试代码
package main
import (
"data_struct/single_link_list"
"fmt"
)
func main(){
fmt.Println("测试单链表")
list := linkedList.List{}
list.Append(1)
list.Append(2)
list.Append(3)
list.Append("a")
list.Append("b")
list.Append("c")
fmt.Printf("链表的长度 %d\n", list.Length())
//fmt.Print("链表当前的内容为:")
//list.ShowList();
//判断链表是否为空
//list2 := linkedList.List{}
//fmt.Printf("list 是否为空链表 : %t\n", list.IsEmpty())
//fmt.Printf("list2 是否为空链表 : %t\n", list2.IsEmpty())
//指定位置插入元素
list.Insert(3, "第三个index的值")
//fmt.Print("链表当前元素内容:")
//list.ShowList();
//测试是否包含某个元素
fmt.Println("是否包含 第三个index的值", list.Contain("第三个index的值"))
//删除元素
//list.Remove("第三个index的值")
//list.ShowList();
//从第三个位置删除
list.RemoveByIndex(3)
list.ShowList()
}
