双向链表

java实现双向链表

package com.scc.demo;

public class MyLinkedList {
    private Node first;// 链表中第一个节点
    private Node last;// 链表中最后一个节点
    private int size;// 节点的数量
    // 创链表中的每一个节点

    class Node {
        Node prev;// 上一个节点对象
        Node next;// 下一个节点对象
        Object ele;// 当前节点 元素
        // 添加一个构造方法可以节点时并赋值

        public Node(Object ele) {
            this.ele = ele;
        }
    }

    // 添加数据的第一位
    public void addFirst(Object ele) {
        Node node = new Node(ele);// 节点对象
        // 如果当前节点是第一次添加(当前节点即是开头也是结尾)
        if (size == 0) {
            this.first = node;
            this.last = node;
        } else {
            // 新节点的下一位是原有的节点
            node.next = this.first;
            // 把新增的节点作为原有节点之前的一个节点
            // 即第一个节点
            this.first.prev = node;
            // 需要开始节点更改
            this.first = node;
        }
        size++;
    }

    // 添加最后一位
    public void addLast(Object ele) {
        // 先创建节点
        Node node = new Node(ele);
        if (size == 0) {
            this.first = node;
            this.last = node;
        } else {
            // 当前节点的下一位是新的节点
            this.last.next = node;
            // 新节点的上一位是原有节点
            node.prev = this.last;
            // 更新新节点为下一个节点
            this.last = node;
        }
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        }
        StringBuffer sbr = new StringBuffer();
        // 获取第一个节点
        sbr.append("[");
        for (int i = 0; i < size - 1; i++) {
            sbr.append(first.ele);
            if (i != size - 1) {
                sbr.append(",");
            } else {
                sbr.append("]");
            }
            first = first.next;// 获取下一个节点
        }
        return sbr.toString();
    }
    // 删除节点
    public void remove(Object ele) {
        // 找到要删除的节点
        Node first = this.first;
        for (int i = 0; i < size; i++) {
            if (!first.ele.equals(ele)) {
                if (first.next == null) {
                    return;
                }
                first = first.next;
            }
        }
        // 删除节点
        if (first == this.first) {
            this.first = first.next;
            this.first.prev = null;
        } else if (first == last) {
            this.last = first.prev;
            this.last.next = null;
        } else {
            // 把删除节点的上一个节点连接删除节点的下一个节点
            first.prev.next = first.next;
            // 把删除节点的下一个节点连接删除节点的上一个节点
            first.next.prev = first.prev;
        }
        size--;
    }
}