单链表及双向链表的代码实现

package linkedList

// 单链表的实现
type ListNode struct {
	Val int
	Next *ListNode
}

type MyLinkedList struct {
	size int
	head *ListNode
}

/*
// initialize struct
func Constructor() MyLinkedList  {
	return MyLinkedList{0, &ListNode{}}
}
 */

func (this *MyLinkedList) Get(index int) int {
	// 通过索引获取链表节点的值
	if index < 0 || index >= this.size {
		return -1
	}

	// 通过前继节点获取
	prev := this.head
	for i:=0;i<index;i++ {
		prev = prev.Next
	}
	return prev.Next.Val
}

func (this *MyLinkedList) AddAtIndex(index int, val int)  {
	// 通过索引插入节点， 先遍历找到前继节点
	if index < 0 || index > this.size {
		return
	}
	// 找到前继节点
	prev := this.head
	for i:=0;i<index;i++ {
		prev = prev.Next
	}
	// 根据给定val生成新节点
	node := &ListNode{Val: val}
	// 防止丢失节点，显然新节点指向prev的下个节点
	node.Next = prev.Next
	// prev指向新节点
	prev.Next = node

	// 更新size
	this.size++
}

func (this *MyLinkedList) AddAtHead(val int)  {
	// 头部插入新节点
	this.AddAtIndex(0, val)
}

func (this *MyLinkedList) AddAtTail(val int)  {
	// 尾部插入新节点
	this.AddAtIndex(this.size, val)
}

func (this *MyLinkedList) DeleteAtIndex(index int)  {
	// 通过索引删除节点， 依然通过前继节点操作，直接指向下下个节点即可
	if index < 0 || index >= this.size {
		return
	}
	// 遍历找到前继节点
	prev := this.head
	for i:=0;i<index;i++ {
		prev = prev.Next
	}
	// 前继指向下下个节点
	prev.Next = prev.Next.Next

	// 更新size
	this.size--
}

//+build ignore
package main

import "fmt"

func main()  {
	head := ConstrutorD()
	head.AddAtHead(2)
	head.AddAtHead(5)
	head.AddAtHead(7)
	head.AddAtIndex(3,4)
	head.AddAtTail(100)
	head.DeleteAtIndex(3)
	fmt.Println(head.Get(0))
	fmt.Println(head.Get(1))
	fmt.Println(head.Get(2))
	fmt.Println(head.Get(3))
}

// 双向链表的实现
type Node struct {
	Val int
	Prev, Next *Node
}

type MyLinkedListD struct {
	size int
	head, tail *Node
}

// initialize struct
func ConstrutorD() MyLinkedListD {
	return MyLinkedListD{}
}

func (this *MyLinkedListD) Get(index int) int {
	// 双向链表，根据索引获取值
	if this.size == 0 || index < 0 || index >= this.size {
		return -1
	}
	// 处理头尾节点，fast-way
	if index == 0 {
		return this.head.Val
	}
	if index == this.size - 1 {
		return this.tail.Val
	}
	// 从头部遍历到index节点
	cur := this.head
	count := 0
	for cur != nil {
		if count == index {
			break
		}
		count++
		cur = cur.Next
	}
	return cur.Val
}

func (this *MyLinkedListD) AddAtIndex(index int, val int)  {
	// 通过索引插入节点
	if index > this.size {
		return
	}
	// 小于0，头部插入
	if index <= 0 {
		this.AddAtHead(val)
		return
	}
	// 尾部插入
	if index == this.size {
		this.AddAtTail(val)
		return
	}
	// 一般情况, 找到index节点
	cur := this.head
	count := 0
	for cur != nil && count < index {
		count++
		cur = cur.Next
	}
	// 生成新节点， 后继节点为cur, 前继节点为cur的前继节点，
	// 相当于  cur.prev<---node--->cur
	node := &Node{Val: val, Next: cur, Prev: cur.Prev}
	cur.Prev.Next = node // cur的前继节点的下个节点指向新节点， --->
	cur.Prev = node // cur的prev指针指向node, <---
	// 更新size
	this.size++
}

func (this *MyLinkedListD) AddAtHead(val int)  {
	// 头部插入
	node := &Node{Val: val}
	if this.head != nil {
		node.Next = this.head // 不断头部
		this.head.Prev = node
		this.head = node // 更新头部
	} else { // 链表为空时
		this.head = node
		this.tail = this.head
	}
	// 更新size
	this.size++
}

func (this *MyLinkedListD) AddAtTail(val int)  {
	// 尾部插入
	node := &Node{Val: val}
	if this.tail != nil {
		node.Prev = this.tail
		this.tail.Next = node
		this.tail = node
	} else {
		this.tail = node
		this.head = this.tail
	}
	// 更新size
	this.size++
}

func (this *MyLinkedListD) DeleteAtIndex(index int)  {
	// 根据索引删除节点
	if this.size == 0 || index < 0 || index >= this.size {
		return
	}
	if index == 0 {
		// 更新头部节点，相当于删除头结点
		this.head = this.head.Next
	} else if index == this.size - 1 {
		// 更新尾部节点，相当于删除尾部节点
		this.tail = this.tail.Prev
	} else {
		// 一般情况, 找到删除节点
		cur := this.head
		count := 0
		for cur != nil && count < index {
			count++
			cur = cur.Next
		}
		cur.Next.Prev = cur.Prev
		cur.Prev.Next = cur.Next
	}
	this.size--
}

posted on 2021-12-14 17:44  Marathon-Davis  阅读(29)  评论(0)  编辑  收藏  举报