基于Java实现双向链表（java实现单向链表的数据结构）

本文实例为大家分享了java实现双向链表的具体代码，供大家参考，具体内容如下

双向链表与单链表的对比：

1、单向链表查找只能是一个方向，双向链表可以向前或者向后查找2、单向链表不能自我删除，需要靠辅助节点**（即需要通过找到要删除的节点的前一个节点，通过该节点进行删除的操作，而双向链表只需找到要删除的节点就行了）**。双向链表可以自我删除

双向链表示意图

分析（代码实现原理）：temp为辅助节点（因为头节点不可动）1、遍历：方式与单链表一致，但是是双向的，可以向前，也可以向后2、添加（默认添加到最后面）（1）先找到链表的最后一个节点（2）temp.next=newnode（3）newnode.pre=temp3、修改：思路与原理与单链表一致4、删除：（1）因为是双向链表，可以自我删除该节点（2）找到要删除的节点，假设这个节点为temp（3）temp.pre.next=temp.next（4）temp.next.pre=temp.pre

添加节点（按顺序）：

步骤：

（1）找到要添加节点位置的前一个节点(temp)（2）node.next=temp.next（3）temp.next.pre=node（4）temp.next=node（5）node.pre=temp

代码实现：

public class DoubleLinkedList {

//创建头结点。表示链表的头

private Node Head=new Node(0,"","");

//返回头结点

public Node getHead() {

return Head;

}

//AddNode1:添加节点到单链表的尾部

//思路：当不考虑节点顺序

//1、找到链表的最后一个节点

//2、将最后这个节点的Next指向新节点

public void AddNode1(Node node) {

//因为头节点不能动，所以需要一个辅助节点遍历

Node temp=Head;

while(true) {

//找到链表的最后一个节点

if(temp.next==null) {

break;

}

//否则temp=temp的下一个节点

temp=temp.next;

}

//循环出来之后，temp是最后一个节点

temp.next=node;

node.pre=temp;

}

//AddNode2:添加节点，按顺序

public void AddNode2(Node node) {

//因为头结点不能动，所以需要一个辅助节点遍历，找到添加新节点的位置

Node temp=Head;

boolean flag=false; //用于标识链表中是否已经存在新节点的顺序

while(true) {

//如果该节点是最后一个节点，则新节点添加到最后一个位置

if(temp.next==null) {

break;

}else if(temp.next.number>node.number) { //说明找到了添加新节点的位置

break;

}else if(temp.next.number==node.number) { //说明新节点的顺序已经存在在链表中

flag=true;

}

temp=temp.next;

}

if(flag) {

System.out.println("该节点的顺序已经存在，插入失败");

}else {

//则说明新节点在链表中不存在，插入新节点

//新节点的下一个节点=辅助节点的下一个节点

node.next=temp.next;

if(temp.next!=null) { //如果temp的下一个节点不为空，则temp的下一个节点的前一个节点为新节点

temp.next.pre=node;

}

//辅助节点的下一个节点=新节点

temp.next=node;

//新节点的前一个节点为辅助节点

node.pre=temp;

}

}

//删除节点

public void remove(Node node) {

if(Head.next==nhttp://ull) {

System.out.println("链表为空！");

return;

}

//创建辅助节点

Node temp=Head.next;

boolean flag=false; //标识是否找到了要删除的节点

while(true) {

if(temp==null) { //遍历完链表了

break;

}else if(temp.number==node.number) { //找到要删除的节点了

flag=true;

break;

}

temp=temp.next;

}

if(flag) { //链表中存在要删除的节点

temp.pre.next=temp.next; //令temp的前一个节点的下一个节点为temp的后一个节点

if(temp.next!=null) { //如果temp不为最后一个节点的话

temp.next.pre=temp.pre; //令temp的下一个节点的前一个节点为temp的前一个节点

}

}else {

System.out.printf("不存在编号为%d的节点",node.number);

}

}

//修改节点，按照节点的Number来修改

public void update(Node newNode) {

if(Head.next==null) {

System.out.println("链表为空！");

return;

}

//创建辅助节点，对链表遍历，知道找到等于修改节点的number的时候

Node temp=Head.next;

boolean flag=false; //用来标识是否找到了修改节点的Number

while(true) {

if(temp==null) { //则已经遍历完链表

break;

}

if(temp.number==newNode.number) {

flag=true;

break;

}

temp=temp.next;

}

if(flag) {

temp.name=newNode.name;

temp.nickName=newNode.nickName;

}else {

System.out.printf("没有找到编号为%d的节点",newNode.number);

}

}

//展示链表

public void show() {

if(Head.next==null) {

System.out.println("链表为空！");

return;

}

//因为头节点不能动，所以通过辅助节点遍历链表

Node temp=Head.next;

while(true) {

//判断是不是最后一个节点

if(temp.next==null) {

System.out.println(temp);

break;

}

System.out.println(temp);

//temp指向下一个节点

temp=temp.next;

}

}

}

//创建节点

class Node{

public int number;

public String name;

public String nickName;

public Node next; //指向下一个节点

public Node pre;//指向前一个节点

//构造器

public Node(int number,String name,String nickName) {

this.number=number;

this.name=name;

this.nickName=nickName;

}

@Override

public String toString() {

return "Node [number=" + number + ", name=" + name + ", nickName=" + nickName + "]";

}

}

测试代码：

public static void main(String[] args) {

// TODO 自动生成的方法存根

Node node1=new Node(1,"宋江","及时雨");

Node node2=new Node(2,"卢俊义","玉麒麟");

Node node3=new Node(3,"吴用","智多星");

Node node4=new Node(4,"林冲","豹子头");

Node node5=new Node(4,"linchong","豹子头");

//创建一个链表

DoubleLinkedList linkedList=new DoubleLinkedList();

linkedList.AddNode2(node1);

linkedList.AddNode2(node3);

linkedList.AddNode2(node4);

linkedList.AddNode2(node2);

linkedList.show();

System.out.println("------------");

linkedListhttp://.remove(node4);

linkedList.show();

}

结果：

Node [number=1, name=宋江, nickName=及时雨]Node [number=2, name=卢俊义, nickName=玉麒麟]Node [number=3, name=吴用, nickName=智多星]Node [number=4, name=林冲, nickName=豹子头]————————————————————————Node [number=1, name=宋江, nickName=及时雨]Node [number=2, name=卢俊义, nickName=玉麒麟]Node [number=3, name=吴用, nickName=智多星]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。