Go语言之单链表实现插入元素

我不是女神ヾ 2022-12-12 15:21 135阅读 0赞

## 单链表简介 ##

单链表是一种顺序存储的结构。  
有一个头结点，没有值域，只有连域，专门存放第一个结点的地址。  
有一个尾结点，有值域，也有链域，链域值始终为NULL。  
所以，在单链表中为找第i个结点或数据元素，必须先找到第i - 1 结点或数据元素，而且必须知道头结点，否则整个链表无法访问。

示例：

### 定义结构体 ###

package main
    
    import "fmt"
    
    type Object interface{ }
    
    type Node struct { 
       Data Object //定义数据域
       Next *Node  //定义地址域(指向下一个表的地址)
    }
    
    type List struct { 
       headNode *Node //头节点
    }

### 判断链表是否为空 ###

//创建IsEmpty方法，返回bool类型
    func (this *List）ISEmpty() bool { 
    
       //判断单链表是否为空，只需要判断头节点是否为空即可
        if this.headNode == nil { 
            return true
        }else { 
             return false
        }
    }

### 获取链表长度 ###

func (this *List) Length() int { 
       //获取链表头结点
       first := this.headNode
       //定义一个计数器，初始值为0
       count := 0
       
       for first != nil { 
          //如果头节点不为空，则count++
          count ++
          //对地址进行逐个位移
          first = first.Next
       }
       return count
    }

### 从链表头部添加元素 ###

func (this *List) Add(data Object) *Node { 
       node := &Node{ Data: data}
       node.Next = this.headNode
       this.headNode = node
       return node
    }

### 从链表尾部添加元素 ###

func (this *List）Append(data object） {     
       
        //创建一个新元素，通过传入data参数进行数据域的赋值
        node := &Node{ Data: data}
        if this.IsEmpty(){ 
            //如果该链表为空，那么直接将新元素作为头节点
           this.headNode=node
        }else { 
             //如果链表不为空
            cur := this.headNode//定义变量用于存储头节点
            
            for cur.Next != nil { //判断是否为尾结点，如果=nil,则该节点是尾节点
                 cur = cur.Next /链表进行位移，知道cur获取到尾节点
             }
    
             cur.Next = node//此时cur为尾节点，将其地址域指向新创建的节点
        }
    }

### 链表指定位置添加元素 ###

//在指定位置添加元素，此处的index指下标，this.headNode的index=0
    func (this *List）Insert(index int,data Object）{ 
        
        if index < o{        //如果index<0，则进行头部插入
            this .Add(data)
        }else if index > this.Length(){      //如果index >链表长度，则进行尾部插入
      		this.Append(data)
        }else { 
             pre := this.headNode
             count := 0
             for count< (index -1){ //用于控制位移的链表数目
     	     pre = pre.Next
      	     count++
             }
         //当循环退出后，pre指向index-1的位置
         node:= &Node{ Data: data} //创建新的链表元素
         node.Next = pre.Next //将新的链表元素地址指向其上一个链表地址域存储的地址(也就是新元素现在的跟随元素)
         pre.Next = node  //上一个链表地址域存储的地址指向新元素地址
    }

### 删除链表指定值的元素 ###

//删除指定元素
    func (this *List) Remove(data Object){ 
       
        pre := this.headNode  //定义变量pre，存储头结点
        
        if pre.Data == data{  //如果该节点的数据域的值为data
            this.headNode = pre.Next //如果就是删除头结点，那么第二个节点就是新的头节点
        }else {    //如果删除的不是头节点
             
             for pre.Next !=nil {   //循环判断是否遍历到最后一个节点，如果不是，则进行如下判断
                
                 if pre.Next.Data == data {   
                 //如果pre.Next的节点的数据等于data，那么删除该节点，pre.Next指向该节点之后的节点地址
                     pre.Next  = pre.Next.Next
                 } else {    //如果pre.Next的节点的数据等于data，那么进行节点位移，循环判断
                        pre = pre.Next
                  }
             }
        }
    }