java数据结构与算法--双端链表链表与双向链表

小鱼儿 2022-05-26 11:43 220阅读 0赞

1、双端链表

package com.evior.linklist;
    
    public class Node {
    
        //数据域
        public long data;
        //指针域
        public Node next;
    
        public Node(long value) {
            this.data=value;
            next=null;
        }
    
        /** * 显示的方法 */ public void  display(){
            System.out.println(data+" ");
        }
    }

package com.evior.linklist2;
    
    import com.evior.linklist.Node;
    
    public class LinkList2 {
    
        //头节点
        private Node first;
    
        //尾节点
    
        private Node last;
    
        public LinkList2(){
            first=null;
            last=null;
        }
    
    
        //插入(从头)
        public void insertFirst(long value){
            Node node=new Node(value);
            if (isEmpty()){
                last=node;
            }
            node.next=first;
            first=node;
        }
    
    
        //插入（从尾）
        public void insertLast(long value){
            Node node=new Node(value);
            if (isEmpty())
            {
                first=node;
            }else {
                last.next=node;
            }
            last=node;
        }
    
        //删除
        public Node deleteFirst(){
            Node temp=first;
            if (first.next==null){
                last=null;
            }
            first=temp.next;
            return temp;
        }
    
        //打印
        public void display(){
            Node current=first;
            while (current!=null){
                current.display();
                current=current.next;
            }
        }
    
    
        //查找的方法
        public Node find(long value){
            Node current=first;
            while (current.data!=value){
                if (current==null){
                    return null;
                }
                current=current.next;
            }
            return current;
        }
    
        //删除方法，根据数据域来进行删除
        public Node delete(long value){
            Node current=first;
            Node previous=first;
            while (current.data!=value){
                if (current==null){
                    return null;
                }
                previous=current;
                current=current.next;
            }
            //判断删除的是否为头结点
            if (current!=first){
                previous.next=current.next;
                current.next=null;
            }else {
                current=first;
                first=current.next;
                current.next=null;
                last=null;
            }
            return current;
        }
    
    
        /** * 判断是否为空 * @return */ public boolean isEmpty(){
            return first==null;
        }
    }

2、测试

package com.evior.linklist2;
    
    public class Test {
    
    
    
        public static void main(String[] args) {
            LinkList2 linkList2=new LinkList2();
    
            linkList2.insertFirst(1);
            linkList2.insertFirst(2);
            linkList2.insertLast(0);
            linkList2.display();
            linkList2.deleteFirst();
            linkList2.display();
            linkList2.delete(1).display();
            linkList2.display();
            linkList2.find(0).display();
        }
    }

3、结果

![70][]

4、双向链表

package com.evior.doublelinklist;
    
    public class Node {
    
        //数据域
        public long data;
        //指针域
        public Node next;
    
        public Node previous;
    
        public Node(long value) {
            this.data=value;
            next=null;
            previous=null;
        }
    
        /** * 显示的方法 */ public void  display(){
            System.out.println(data+" ");
        }
    }

package com.evior.doublelinklist;
    
    public class DoubleLinkList {
    
        //头结点
        private Node first;
    
    
        //尾节点
        private Node last;
    
    
        public DoubleLinkList(){
            first=null;
            last=null;
        }
    
    
        /** * 插入一个结点，在头结点后进行插入 * @param value */ public void insertFirst(long value){
            Node node=new Node(value);
            //判断是否为空
            if (isEmpty()){
                last=node;
            }else {
                first.previous=node;
            }
            node.next=first;
            first=node;
        }
    
    
        /** * 插入一个结点，从尾结点进行插入 */ public void insertLast(long value){
            Node node=new Node(value);
            if (isEmpty()){
                first=node;
                last=node;
            }else {
                last.next=node;
                node.previous=last;
                last=node;
            }
    
        }
    
    
        /** * 删除头节点 * @return */ public Node deleteFirst(){
            Node current=first;
            if (first.next==null){
                last=null;
                first=null;
                return current;
            }else {
                first.next.previous=null;
                first=current.next;
                return current;
            }
        }
    
    
        /** * 删除尾节点 * @return */ public Node deleteLast(){
            Node current=last;
            if (current.previous==null){
                last=null;
                first=null;
                return current;
            }else {
                current.previous.next=null;
                last=current.previous;
                return current;
            }
        }
    
    
        /** * 显示方法 */ public void display() {
            Node current = first;
            while(current != null) {
                current.display();
                current = current.next;
            }
            System.out.println();
        }
    
    
        /** * 查找 */ public Node find(long value){
            Node current=first;
            while (current.data!=value){
                if (current.next==null){
                    return null;
                }
                current=current.next;
            }
            if(current == first) {
                first = first.next;
            } else {
                current.previous.next = current.next;
            }
            return current;
    
        }
    
    
        /** * 判断是否为空 */ public boolean isEmpty() {
            return (first == null);
        }
    
    }

5、测试

package com.evior.doublelinklist;
    
    public class Test {
    
        public static void main(String[] args) {
            DoubleLinkList doubleLinkList=new DoubleLinkList();
            doubleLinkList.insertFirst(1);
            doubleLinkList.insertFirst(2);
    
            doubleLinkList.insertLast(3);
            doubleLinkList.insertLast(4);
    
            doubleLinkList.display();
            doubleLinkList.deleteFirst();
            doubleLinkList.display();
            doubleLinkList.deleteLast();
            doubleLinkList.display();
    
            doubleLinkList.find(1).display();
        }
    }

6、结果

![70 1][]

[70]: /images/20220526/0aa1c8d4d1fb4c20b30343df165d0003.png
[70 1]: /images/20220526/acb3c2d4bbbd4b32afa3e2dc76d5b4a7.png