java手写双链表
双链表
链表中的每个节点即指向前面一个节点，也指向后面一个节点，就像丢手绢游戏一样，每个人都手拉手 。简单来说，双向链表其实和单链表类似的，只是在定义存储结构时多了一个指向前驱结点，删除时只要更新当前的结点指向的前驱结点的下一个结点为当前结点的下一个结点即可，
头插法
这里看图就行了
这里图写错了，我这种应该不是第一次插入的场景，第一次插入头和尾结点直接指向node，当第二次的时候
node.next = this.head;//直接引导，让node2指向node
this.head.prev=node;//回溯，使得node回向node2，单链表时候这个可以去掉
this.head=node;//为下次做铺垫尾插法
尾插法这里图也画错了，
this.tail.next = node;//这里直接node.next=node2
node.prev=this.tail;//node2.prev = node
this.tail=node;//为下次做铺垫不得不说，这个java的双链表比c++要简单多了
代码
package zy_2021_12.doubleLink;
class Node{
public int data;//数据
public Node next;//后继信息
public Node prev;//前驱信息
//提供构造方法
public Node(int data){
this.data = data;
}
}
public class DoubleLinkedList {
public Node head; //表示双向链表的头
public Node tail; //表示当前双向链表的尾
//1.打印链表
//记住，尾插法遍历值，也是从头结点开始，如果是单链表，那么尾插法需要一个头结点
public void print(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
//2.头插法
public void addFirst(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//3.尾插法
public void addLast(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
private void checkIndex(int index){
if(index < 0 || index > len()){
throw new RuntimeException("index不合法！！");
}
}
private Node searchIndex(int index){
Node cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//4.任意位置插入，第一个数据节点为0号下标
public void addIndex(int index,int data){
checkIndex(index);
if(index == 0){
addFirst(data);
return;
}
if(index == len()){
addLast(data);
return;
}
Node node = new Node(data);
Node cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
//5.查找链表中是否包含关键字 key
public boolean containKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
//6.删除第一次出现关键字为 key 的节点
public void deleteKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//头节点
if(cur == this.head){
this.head = this.head.next;
this.head.prev = null;
}
//中间节点
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//删除的是尾节点,只需要移动tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//7.删除所有关键字为 key 的节点
public void deleteAllKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//头节点
if(cur == this.head){
this.head = this.head.next;
if(this.head != null){
this.head.prev = null;
}
}
//中间节点
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//删除的是尾节点,只需要移动tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//8.链表长度
public int len(){
int count = 0;
Node cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
//9.链表清空
public void clear(){
//一个一个节点进行释放
while(this.head != null){
Node cur = this.head.next;
this.head.prev = null;
this.head.next = null;
this.head = cur;
}
this.tail = null;
}
//根据index移除数据
public int remove(int index){
int data;
checkIndex(index);
Node cur = this.head;
//找到index+1个结点
while(index-1 != 1) {
cur = cur.next;
index--;
}
if(cur==null)
return 0;//表示index越界
else{
Node tmp = cur.next;//tmp代表要删除的结点
if(tmp==null)
return 0;
data = tmp.data;
cur.next = tmp.next;
//java中不需要释放对象，由jvm虚拟机管理
}
return data;
}
}主main测试
package zy_2021_12.doubleLink;
import zy_2021_12.doubleLink.zy.DoubleLinkedList2;
import java.util.Scanner;
/**
* @date 2021/11/30 9:01
*/
public class Main {
public static void main(String[] args) {
DoubleLinkedList2 doubleLinkedList = new DoubleLinkedList2();
Scanner sc = new Scanner(System.in);
System.out.println("头插法插入值1，2，3");
System.out.println(doubleLinkedList.insertFirst(1));
System.out.println(doubleLinkedList.insertFirst(2));
System.out.println(doubleLinkedList.insertFirst(3));
System.out.println("插入后的结果:");
doubleLinkedList.print();
System.out.println("尾插法插入值4，5，6");
System.out.println(doubleLinkedList.insertLast(4));
System.out.println(doubleLinkedList.insertLast(5));
System.out.println(doubleLinkedList.insertLast(6));
System.out.println("插入后的结果:");
doubleLinkedList.print();
System.out.println("请输入你要插入的结点之后的位置(insertAfter)和要插入的数据");
doubleLinkedList.insertAfter(sc.nextInt(),sc.nextInt());
System.out.println("插入后的结果：");
doubleLinkedList.print();
System.out.println("请输入你要插入的结点之前的位置(insertBefore)和要插入的数据");
doubleLinkedList.inserBefore(sc.nextInt(),sc.nextInt());
System.out.println("插入后的结果：");
doubleLinkedList.print();
System.out.println("请输入你要删除的结点的位置(remove)");
int data = doubleLinkedList.remove(sc.nextInt());
System.out.println("被删除的数据："+data);
System.out.println("删除后结果");
doubleLinkedList.print();
}
}总结
这里我有个概念混淆了，双链表是双链表是结点1和2能相互指向的链表，和头插入和尾插入没关系，但是双链表却是需要两个结点，一个从头遍历，一个从尾遍历嘛
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：java手写双链表
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
