亲宝软件园·资讯

展开

Java双向链表

fan儿 人气:0

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

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

双向链表示意图

分析(代码实现原理):temp为辅助节点(因为头节点不可动)
1、遍历:方式与单链表一致,但是是双向的,可以向前,也可以向后
2、添加(默认添加到最后面)
(1)先找到链表的最后一个节点
(2)temp.next=newnode
(3)newnode.pre=temp
3、修改:思路与原理与单链表一致
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==null) {
            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("------------");
        linkedList.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=智多星]

加载全部内容

相关教程
猜你喜欢
用户评论