数据集结构之双向链表

双向链表也叫头尾链表，头尾链表可以在头结点和尾结点分别进行插入和删除操作

首先建立结点类，代码如下：

package firstlastlist;

public class Node{
    int data; //数据
    public Node next;  //节点下一个值
    public Node privious;  //节点上一个值
    public Node(int value){
        this.data=value;

    }
    public void display(){
        System.out.println(data+" ");
    }
}

操作代码：

package firstlastlist;
public class FirstLastList {
    Node first;//头结点
    Node last;//尾结点
    public FirstLastList(){
        first=null;
        last=null;
    }
    public boolean isEmpty(){
        return first==null;
    }
    public void insertFirst(int value){//插入元素，在头结点前面插入
        Node node=new Node(value);
        if(isEmpty()){
            last=node;
        }

        node.next=first;
        first=node;
    }
    public void insertlast(int value){//从尾结点插入
        Node node=new Node(value);
        if(isEmpty()){
            first=node;
        }
        else{
            last.next=node;//从尾结点插入
        }
        last=node;
    }
    public int deletFirst(){//删除元素，从头结点开始
        if(first.next==null){//如果头结点的下一个结点为空，则只剩一个结点，此时将尾结点置为空，以便下次使用
            last=null;
        }
        Node temp=first;
        first=first.next;//把后面的结点往前移进行删除，最后剩一个结点时first和last均为null
        return temp.data;
    }
    public void display(){//打印链表的数据，从头结点开始
        Node t=first;
        while(t.next!=null){
            t.display();
            t=t.next;
        }
        //当t的下一个结点为null时，此时t到了尾结点，然后跳出循环，打印尾结点
        t.display();;
    }
    public Node chazhao(int value){//按值查找
        Node tt=first;
        while(tt.data!=value){//当tt结点的值不符合要求时，往他的邻结点查找
            if(tt.next==null){//当结点的值不符合且后面也没有结点时，则返回null，没找到
                return null;
            }
            tt=tt.next;
        }
        return tt;
    }
    public Node shangchu(int value){//按值删除并输出值
        Node tt=first;
        Node ty=first;//ty作为新一个tt的上一个结点，用来进行删除操作
        while(tt.data!=value){
            if(tt.next==null){
                return null;
            }
            ty=tt;
            tt=tt.next;
        }
        if(tt==first){
            first=first.next;
        }
        else{
            ty.next=tt.next;//把该节点前一个结点的下一个结点值变为该节点的下一个结点，即完成了删除操作
        }
        return tt;
    }
}

测试代码：

package firstlastlist;


public class TestFirstlastList {
    public static void main(String args[]){
        FirstLastList tt=new FirstLastList();
        tt.insertFirst(1);
        tt.insertFirst(2);
        tt.insertFirst(3);
        tt.display();
        tt.deletFirst();
        tt.display();
    }
}