import "fmt"
/*
实现单链表
- append
- 结点前后插入
- 依值查找
- 删除结点
- 打印链表值
*/
type ListNode struct {
Val interface{}
Next *ListNode
}
type LinkedList struct {
head *ListNode
size int
}
// 创建结点
func newNode(val interface{}) *ListNode {
return &ListNode{
Val: val,
Next: nil,
}
}
func New() *LinkedList {
return &LinkedList{
head: nil,
size: 0,
}
}
//添加至链尾 并返回生成的结点
func (lists *LinkedList) PushBack(val interface{}) *ListNode {
head := lists.head
// 将待插入值转化为 node
node := newNode(val)
if head == nil {
lists.head = node
} else {
for head.Next != nil {
head = head.Next
}
head.Next = node
}
lists.size++
return node
}
//结点前插入
func (lists *LinkedList) PushBefore(p *ListNode, val interface{}) *ListNode {
if p == nil || lists.head == nil {
return nil
}
node := newNode(val)
// 在头结点之前插入情况
if p == lists.head {
node.Next = lists.head
lists.head = node
} else {
prev := lists.head
// 找到待插入节点的前一个节点
for ; prev.Next != p; prev = prev.Next {
}
node.Next = p
prev.Next = node
}
lists.size++
return node
}
//结点后插入
func (lists *LinkedList) PushAfter(p *ListNode, val interface{}) *ListNode {
if p == nil {
return nil
}
node := newNode(val)
node.Next = p.Next
p.Next = node
lists.size++
return node
}
//查找结点
func (lists *LinkedList) Find(val interface{}) *ListNode {
cur := lists.head
for cur != nil && cur.Val != val {
cur = cur.Next
}
return cur
}
//删除指定结点
func (lists *LinkedList) Delete(p *ListNode) {
if p == nil {
return
}
if p == lists.head {
// 待删结点为头结点
lists.head = lists.head.Next
lists.size--
} else {
// 非删除头结点时 找到待删结点的 prev 结点
prev := lists.head
for prev != nil && prev.Next != p {
prev = prev.Next
}
// 保证找到 而非 prev 走到链尾
if prev != nil {
prev.Next = p.Next
lists.size--
}
}
}
//删除指定值结点 调用 find 找到指定值的结点再删除结点即可
func (lists *LinkedList)DeleteVal(val interface{}) {
lists.Delete(lists.Find(val))
}
//打印链表值
func (lists *LinkedList)PrintDara() {
if lists.size==0 {
return
}
for node:=lists.head;node!=nil;node = node.Next {
fmt.Print(node.Val," ")
}
fmt.Println()
}
package doublyLinkedlist
import "fmt"
/*
实现双向链表
- CRUD
- 表头和表尾的追加
*/
type ListNode struct {
Val interface{}
prev,next *ListNode
}
type LinkedList struct {
head *ListNode
size int
}
func New()*LinkedList {
return & LinkedList {
head: nil,
size: 0,
}
}
// 插入到表头 区分表头是否空
func (lists * LinkedList)PushFront(val interface{}) *ListNode {
node:=newNode(val)
if lists.head!=nil {
lists.head.prev=node
node.next=lists.head
}
lists.head=node
lists.size++
return node
}
func newNode(val interface{}) *ListNode{
return & ListNode {
Val: val,
prev: nil,
next: nil,
}
}
// 插入数据到链尾
func (lists * LinkedList) PushBack(val interface{}) *ListNode{
// 空表则调用链首插入
if lists.head==nil {
lists.PushFront(val)
}
node:=newNode(val)
cur:=lists.head
for cur.next != nil {
cur=cur.next
}
cur.next=node
node.prev=cur
lists.size++
return node
}
//节点后插入数据
func (lists * LinkedList) PushAfter(p *ListNode, val interface{}) *ListNode {
if p==nil {
return nil
}
// 找到要插入位置的前后结点
next:=p.next
node:=newNode(val)
// 插入 注意判断 next 为空时next.prev 不存在 无须链接 新插入的 node 即为最后一个节点
node.next=next
p.next=node
node.prev=p
if next!=nil {
next.prev=node
}
lists.size++
return node
}
//结点前插入数据
func (lists * LinkedList)PushBefore(p *ListNode,val interface{}) *ListNode {
if p==nil {
return nil
}
node:=newNode(val)
prev:=p.prev
// 待插入的链表为空则调用链首插入函数
if prev==nil {
lists.PushFront(val)
}else {
// 在指定结点前插入需找到prevNode
p.prev=node
node.next=p
prev.next=node
node.prev=prev
lists.size++
}
return node
}
//删除结点
func (lists * LinkedList) Delete(p *ListNode) {
if p == nil|| lists.head==nil {
return
}
// 删除结点为头结点则直接跳过即可
if p==lists.head {
lists.head=p.next
}else {
// 注意待删结点的 nextNode 为链尾空节点时 无须链接 nextNode.prev=prevNode
prevNode,nextNode:=p.prev,p.next
prevNode.next=nextNode
if nextNode!=nil {
nextNode.prev=prevNode
}
}
lists.size--
}
//依值查找结点
func (lists * LinkedList)Find(val interface{}) *ListNode {
if lists.head==nil{
return nil
}
cur:=lists.head
for cur!=nil&&cur.Val!=val {
cur=cur.next
}
return cur
}
//打印链表数据
func (lists * LinkedList)PrintDara() {
for p:=lists.head;p!=nil;p=p.next {
fmt.Print(p.Val," ")
}
fmt.Println()
}
func (lists * LinkedList)Size() int {
return lists.size
}