双链表算法

た入场券 2023-07-12 14:42 92阅读 0赞

*  双链表最大的优势就是可以双向遍历

package main
    
    import "fmt"
    
    type Node struct { 
    	num  int
    	name string
    	pre  *Node
    	next *Node
    }
    
    // 末尾插入
    func insert(head *Node, newNode *Node) { 
    	tmp := head
    	for { 
    		// 插入末尾，先连接左边，后连接右边
    		if tmp.next == nil { 
    			tmp.next = newNode
    			newNode.pre = tmp
    			break
    		}
    		tmp = tmp.next
    	}
    }
    
    // 正向遍历
    func list(head *Node) { 
    	tmp := head
    	if tmp.next == nil { 
    		fmt.Printf("link is null")
    	}
    
    	for { 
    		if tmp.next != nil { 
    			// 第一个tmp代表head的下一个
    			fmt.Printf("[%d] = %s \n", tmp.next.num, tmp.next.name)
    		} else { 
    			break
    		}
    		tmp = tmp.next
    	}
    }
    
    // 反向遍历
    func reverselist(head *Node) { 
    	tmp := head
    	if tmp.next == nil { 
    		fmt.Printf("link is null")
    	}
    	// 先将tmp指向链表末尾
    	for { 
    		if tmp.next == nil { 
    			break
    		}
    		tmp = tmp.next
    	}
    
    	for { 
    		// 注意头节点并不是空的，里面还有mext和pre
    		if tmp.pre != nil { 
    			fmt.Printf("[%d] = %s \n", tmp.num, tmp.name)
    		} else { 
    			break
    		}
    		tmp = tmp.pre
    	}
    }
    
    func main() { 
    	// head是随机位置的指针
    	head := &Node{ }
    
    	// 插入数据不需传递下一个node地址
    	node := &Node{ 
    		num:  1,
    		name: "amber",
    	}
    	node2 := &Node{ 
    		num:  2,
    		name: "alice",
    	}
    	node3 := &Node{ 
    		num:  3,
    		name: "necy",
    	}
    	node4 := &Node{ 
    		num:  4,
    		name: "bella",
    	}
    
    	insert(head, node)
    	insert(head, node2)
    	insert(head, node3)
    	insert(head, node4)
    
    	list(head)
    	fmt.Println()
    	reverselist(head)
    
    }

输出结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70]

*  双链表有序插入和删除

package main
    
    import "fmt"
    
    type Node struct { 
    	num  int
    	name string
    	pre  *Node
    	next *Node
    }
    
    func orderInsert(head *Node, newNode *Node) { 
    	tmp := head
    	for { 
    		// 必须放在前面，防止在末尾nil，被插在最后
    		if newNode.num == tmp.num { 
    			fmt.Printf("node has already in link\n")
    			break
    		}
    		// 放在第二顺位，当未找到插入最后
    		if tmp.next == nil { 
    			tmp.next = newNode
    			newNode.pre = tmp
    			break
    		}
    		// 遍历是从前往后，判断条件tmp.next是保证在tmp后面插入前插入
    		if newNode.num < tmp.next.num { 
    			// 先关联右边，再关联左边
    			newNode.next = tmp.next
    			newNode.pre = tmp
    
    			tmp.next.pre = newNode
    			tmp.next = newNode
    			break
    		}
    
    		tmp = tmp.next
    	}
    
    }
    
    func list(head *Node) { 
    	tmp := head
    	if tmp.next == nil { 
    		fmt.Printf("link is null")
    	}
    
    	for { 
    		if tmp.next != nil { 
    			// 第一个tmp代表head的下一个
    			fmt.Printf("[%d] = %s \n", tmp.next.num, tmp.next.name)
    		} else { 
    			break
    		}
    		tmp = tmp.next
    	}
    }
    
    func delete(head *Node, num int) { 
    	tmp := head
    	for { 
    		if tmp == nil { 
    			fmt.Printf("link is null")
    			break
    		}
    		// 注意这里要找到tmp.next，因为找到tmp是要删除节点无法删除
    		if tmp.num == num { 
    			if tmp.next == nil { 
    				tmp.pre.next = nil
    				break
    			} else { 
    				tmp.next.pre = tmp.pre
    				tmp.pre.next = tmp.next
    				break
    			}
    		}
    		tmp = tmp.next
    
    	}
    }
    
    func main() { 
    	// head是随机位置的指针
    	head := &Node{ }
    
    	// 插入数据不需传递下一个node地址
    	node := &Node{ 
    		num:  1,
    		name: "amber",
    	}
    	node2 := &Node{ 
    		num:  2,
    		name: "alice",
    	}
    	node3 := &Node{ 
    		num:  3,
    		name: "necy",
    	}
    	node4 := &Node{ 
    		num:  3,
    		name: "zoe",
    	}
    
    	orderInsert(head, node4)
    	orderInsert(head, node2)
    	orderInsert(head, node)
    	orderInsert(head, node3)
    	list(head)
    
    	fmt.Printf("****************\n")
    
    	delete(head, 2)
    	list(head)
    
    }

输出结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 1]  
PS：这里演示的是重复插入在最后的情况，所以要将重复判断放在末尾插入之前

总结：  
1、无论单链表还是双链表插入一定定位在tmp和tmp.next之间  
2、头节点数据是空的，但不代表头节点=nil  
3、删除和插入是一定要考虑删除的恰好是最后的节点或者插入到最后的情况

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309122101456.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309135205457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70