数据结构之双端链表

﹏ヽ暗。殇╰゛Y 2022-06-18 11:26 210阅读 0赞

双端链表指的是双向链表中头结点始终保持着对尾结点的引用。  
准备数据：  
一、结点类：

/** * 链表节点，相当于火车的车厢 * @author Administrator * */
    public class MyNode { 
    
        //数据域
        public  long data;
    
        //指针域
        public  MyNode next;
    
        /** * 前指针域 */
        public MyNode previous;
    
        /** * 创建节点，数据域赋值 * @param value */
        public MyNode(long value){
            this.data=value;
        }
    
        public void display(){
            System.err.print(data+" ");
        }
    }

二、双端链表类

/** * 双端链表，始终保持着对尾结点的引用 * @author Administrator * */
    public class MyFirstLastLink { 
    
        /** * 头结点 */
        private MyNode first;
    
        private MyNode last;
    
        /** * 构造方法 */
        public MyFirstLastLink(){
            first=null;
            last=null;
        }
    }

1、插入结点  
（1）、在头结点后插入节点,如果链表为空，则设置尾结点为新增节点

/** * 在头结点后插入节点,如果链表为空，则设置尾结点为新增节点 * @param value */
        public void insetFirst(long value){
            MyNode node=new MyNode(value);
            if (isEmpty()) {
                last=node;
            }
            node.next=first;
            first=node;
        }

（2）、插入结点，从尾结点插入

/** * 插入结点，从尾结点插入 * @param value */
        public void insertLast(long value){
            MyNode node=new MyNode(value);
            if (isEmpty()) {
                first=node;//若链表为空，则设置头结点为新增节点
            }else {
                last.next=node;//若链表不为空，则设置尾结点的下一个节点为新增结点
            }
            last=node;
        }

（3）、根据关键字插入结点

/** * 在关键字之后插入结点 * @param value * @param key */
        public void insertFindByKey(long value,long key){
            MyNode curNode=find(key);
            if (curNode==null) {
                System.out.println("未找到插入结点的位置");
            }else {
                MyNode node=new MyNode(value);//要插入的结点
                node.previous=curNode;
                node.next=curNode.next;
                node.previous.next=node;
                node.next.previous=node;
            }
        }

2、删除结点：  
（1）、删除头结点后的节点,从头部开始删除

/** * 删除头结点后的节点,从头部开始删除 * 判断头结点是否有下一个结点，如果没有则设置为节点为null * @return */
        public MyNode deleteFirst(){
            MyNode temp=first;//头结点
            if (first.next==null) {
                last=null;
            }
            first=temp.next;
            return temp;
        }

（2）、根据关键字删除结点

/** * 删除 * @param value * @return */
        public MyNode delete(long value){
            MyNode currNode=first;
            MyNode previous=first;
            while(currNode.data!=value){
                if (currNode.next==null) {
                    return null;
                }
                previous=currNode;
                currNode=currNode.next;
            }
            if (currNode==first) {
                first=first.next;
            }else {
                previous.next=currNode.next;
            }
            return currNode;
        }

3、根据关键字查找结点

/** * 查找方法 * @param value * @return */
        public MyNode find(long value){
            MyNode currNode=first;
            while(currNode!=null){
                if (currNode.data==value) {
                    return currNode;
                }
                currNode=currNode.next;
            }
            return null;
        }

4、显示所有结点

/** * 显示结点 */
        public void display(){
            MyNode currNode=first;
            while(currNode!=null){
                currNode.display();
                currNode=currNode.next;
            }
        }

5、判断链表是不是为空

/** * 判断是否为空 * @return */
        public boolean isEmpty(){
            return first==null;
        }