java实现单链表(双向链表数据结构)

//节点
class ListNode {
    public int data;//数据
    public ListNode prev;//指向上一个节点
    public ListNode next;//指向下一个节点

    public ListNode(int data) {
        this.data = data;
    }
}
//双链表
public class DoublelinkedList {
    public ListNode dummyHead;//头指针
    public ListNode last;//尾指针
    
    public DoublelinkedList() {
        this.dummyHead = new ListNode(-1);
    }
    //返回index位置的节点
    public ListNode findIndex(int index) {
        ListNode cur = dummyHead.next;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //向链表头添加节点
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(this.dummyHead.next==null) {
            node.prev=this.dummyHead;
            this.dummyHead.next=node;
            this.last=node;
            return;
        }else {
            node.next=this.dummyHead.next;
            node.prev=this.dummyHead;
            this.dummyHead.next.prev=node;
            this.dummyHead.next=node;
        }
    }
    //向链表尾添加节点
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(this.dummyHead.next==null&&this.last==null) {
            node.prev=this.dummyHead;
            this.dummyHead.next=node;
            this.last=node;
            return;
        }else {
            this.last.next=node;
            node.prev=this.last;
            this.last=node;
        }
    }
    //向链表index位置添加节点
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("输入的位置不合法");
            return;
        } else {
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index == size()) {
                addLast(data);
            }else {
                ListNode node = new ListNode(data);
                ListNode cur;
                cur = findIndex(index);
                cur.prev.next = node;
                node.prev = cur.prev;
                cur.prev = node;
                node.next = cur;
            }
        }
    }
    //判断链表中是否有值为key的节点
    public boolean contains(int key) {
        ListNode cur = this.dummyHead.next;
        while (cur != null) {
            if (cur.data == key) return true;
            cur=cur.next;
        }
        return false;
    }
    //删除链表中首个值为key的节点
    public void remove(int key) {
        ListNode cur = this.dummyHead.next;

        while(cur != null) {
            if(cur.data == key) {
                if(cur == this.dummyHead.next) {
                    this.dummyHead.next = this.dummyHead.next.next; 
                    this.dummyHead.next.prev = this.dummyHead;
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = cur.prev;
                    }
                }
                return;
            } else {
                cur = cur.next;
            }
        }
    }
    //删除链表中所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = dummyHead.next;
        while (cur != null) {
            //
            if (cur.data == key) {
                if (cur == this.dummyHead.next) {
                    this.dummyHead.next=this.dummyHead.next.next;
                    this.dummyHead.next.prev=null;

                } else {
                    cur.prev.next = cur.next;
                    //判断是不是最后一个节点
                    if (cur.next == null) {
                        this.last = cur.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    //返回链表中节点个数
    public int size() {
        ListNode cur =this.dummyHead.next;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
	//显示链表中所有的数据
    public void display() {

        ListNode cur = this.dummyHead.next;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;

        }
        System.out.println();

    }
	//清空链表
    public void clear() {
        ListNode cur =  this.dummyHead.next;
        ListNode curNext;
        while (cur != null) {
            curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.dummyHead = null;
        this.last = null;
    }
    
}