数据结构--双链表

双链表特点：结点双向指引，即在当前结点情况下，可以知道上一结点，也可知道下一结点

---

public class DLinkListClass<E>{ 
    static class DLinkNode<E>{  
        E data;		//存放数据	
        DLinkNode<E> prior;		//前驱指针
        DLinkNode<E> next;		//后驱指针

        /**
        初始化结点
        **/
        public DLinkNode(){  
            prior=null;
            next=null;
        }
        public DLinkNode(E d){  
            data=d;
            prior=null;
            next=null;
        }
    }

    DLinkNode<E> dhead;			//头结点

    /**
    初始化双链表
    **/
    public DLinkListClass(){  
        dhead=new DLinkNode<E>();
        dhead.prior=null;
        dhead.next=null;
    }

    /**
    头插法数组整体添加
    **/
    public void createListFront(E[] a){  
        DLinkNode<E> s;
        //循环建立数据结点s
        for (int i=0;i<a.length;i++){	
            //新建存放a[i]元素的结点s，将其插入到表头
            s=new DLinkNode<E>(a[i]);	
            //修改s结点的next成员
            s.next=dhead.next;		
            //修改头结点的非空后继结点的prior成员
            if (dhead.next!=null){
                dhead.next.prior=s;
            }	
            //修改头结点的next成员
            dhead.next=s;	
            //修改s结点的prior成员
            s.prior=dhead;		
        }
    }

    /**
    尾插法数组整体添加
    **/
    public void createListRear(E[] a){  
        DLinkNode<E> s,t;
        //t始终指向尾结点
        t=dhead;	
        //循环建立数据结点s
        for (int i=0;i<a.length;i++){  
            //新建存放a[i]元素的结点s
            s=new DLinkNode<E>(a[i]);		
            //将s结点插入t结点之后
            t.next=s;				
            s.prior=t; 
            t=s;
        }
        //将尾结点的next成员置为null
        t.next=null;			
    }

    /**
    尾插法单个添加
    **/
    public void addNodeRear(E value){
        DLinkNode s=new DLinkNode<E>(value);
        DLinkNode temp = dhead;
        //用于判断是否到最后节点
        boolean isFlag = false;
        while (true) {
            if (temp.next == null) {
                isFlag = true;
                break;
            }
            temp = temp.next;
        }
        //到最后一个节点
        if (isFlag) {
            temp.next = s;
            hero.prior = temp;
        } else {
            System.out.println("添加失败");
        }		
    }

    /**
     * 找到序号为i的结点
     */
    public DLinkNode geti(int i){
        DLinkNode temp=dhead;
        for (int j = 0; j < i; j++) {
            temp=temp.next;
        }
        return temp;
    }

    /**
     * 在序号为i的位置上插入值为e的元素
     */
    public void insert(int i, E e){  
        if (i<0 || i>size()){
            //参数错误抛出异常
            throw new IllegalArgumentException("插入:位置i不在有效范围内");
        }			
        //建立新结点s
        DLinkNode<E> s=new DLinkNode<E>(e);		
        //找到序号为i-1结点p,其后插入s结点
        DLinkNode<E> p=geti(i-1);
        //修改s结点的next成员		
        s.next=p.next;		
        //修改p结点的非空后继结点的prior成员	
        if (p.next!=null){
            p.next.prior=s;
        }			
        //修改p结点的next成员
        p.next=s;	
        //修改s结点的prior成员			
        s.prior=p;				
    }

    /**
     * 删除序号为i的元素
     */
    public void delete(int i) {  
        //参数错误抛出异常
        if (i<0 || i>size()-1){
            throw new IllegalArgumentException("删除:位置i不在有效范围内");
        }	
        //找到序号为i的结点p,删除该结点
        DLinkNode<E> p=geti(i);		
        //修改p结点非空后继结点的prior成员
        if (p.next!=null){
            p.next.prior=p.prior;
        }	
        //修改p结点的前驱结点的next成员
        p.prior.next=p.next;			
    }

    /**
    * 遍历双链表
    */
    public void list() {
        if (dhead.next==null){
            System.out.println("链表为空");
        }
        DLinkNode temp = dhead.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

---

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/02f84d0824.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！