手动实现java常用的容器-linkedList

手动实现java常用的容器-linkedList

  (方法只是模拟java源码,效率没有底层源码高,纯属学习熟悉底层源码)

单个节点结构图

容器结构图

节点源码

package com.alan.alanlinkedlist;

/**
 * author Mr.ALan
 * DESCRIPTION 自定义列表的单个节点 双向列表
 * create 2019/4/11
 */

public class Node<E> {
    //  用处存放数据的 地址值(引用数据)
    private E value;

    // 存放上一个节点的 地址值
    private Node previous;

    // 存放下一个节点的 地址值
    private Node next;

    // 只存放值的构造
    public Node(E value) {
        this.value = value;
    }

    // 满参构造
    public Node(E value, Node previous, Node next) {
        this.value = value;
        this.previous = previous;
        this.next = next;
    }

    // 获取当前节点的值
    public E getValue() {
        return value;
    }

    // 设置当前节点的值
    public void setValue(E value) {
        this.value = value;
    }

    // 获取上一个节点
    public Node getPrevious() {
        return previous;
    }

    // 替换上一个节点(指向的是新的节点,原本的节点如果没有引用会成为垃圾)
    public void setPrevious(Node previous) {
        this.previous = previous;
    }

    // 获取下一个节点
    public Node getNext() {
        return next;
    }

    // 替换下一个节点
    public void setNext(Node next) {
        this.next = next;
    }
}

容器源码

package com.alan.alanlinkedlist;

/**
 * author Mr.ALan
 * DESCRIPTION
 * create 2019/4/11/
 */
@SuppressWarnings("all")
public class AlanLinkedList<E> {
    /**
     * 链表的其他节点
     * 通过frist的next直接指向或简介指向
     * 或者last的previous直接指向或间接指向
     */

    // 链表中的第一个节点对象  (E value, Node previous, Node next)
    Node frist;

    // 链表中的最后一个节点对象  (E value, Node previous, Node next)
    Node last;

    // 用于记录节点中有效的节点个数
    private int size;

    // 五参数构造
    public AlanLinkedList() {

    }

    // 检查索引是否存在越界情况
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("索引越界");
        }

    }

    // 在第一个位置添加元素
    public void addFrist(E element) {
        Node newNode = new Node(element);
        if (frist == null) {
            frist = newNode;
            last = newNode;
        } else {
            newNode.setNext(frist);
            frist.setPrevious(newNode);
            frist = newNode;
        }
        size++;
    }

    // 在最后一个位置添加元素
    public void addlast(E element) {
        Node newNode = new Node(element);
        if (frist == null) {
            frist = newNode;
            last = newNode;
        } else {
            last.setNext(newNode);
            newNode.setPrevious(last);
            last = newNode;
        }
        size++;
    }

    // 默认情况的添加 在最后添加
    public void add(E element) {
        addlast(element);
    }

    // 在指定的位置添加元素
    public void add(int index, E element) {
        // 在最后插入元素
        if (index == size) {
            addlast(element);
            return;
            // 在第一位插入元素
        } else if (index == 0) {
            addFrist(element);
            return;
        }

        checkIndex(index);
        Node newNode = new Node(element);
        Node tempNode = getNode(index);
        Node lastNode = tempNode.getPrevious();
        // 在中间插入新的元素
        if (tempNode != null && lastNode != null) {
            lastNode.setNext(newNode);
            newNode.setPrevious(lastNode);
            newNode.setNext(tempNode);
            tempNode.setPrevious(newNode);
        }
        size++;
    }

    // 获取第一个元素
    public E getFrist() {
        return (E) frist.getValue();
    }

    // 获取最后一个元素
    public E getLast() {
        return (E) last.getValue();
    }

    // 获取指定位置的元素
    public E get(int index) {
        checkIndex(index);
        Node tempNode = frist;
        for (int i = 0; i < index; i++) {
            tempNode = tempNode.getNext();
        }
        return (E) tempNode.getValue();
    }

    // 获取指定位置的元素节点对象
    private Node getNode(int index) {
        checkIndex(index);
        Node tempNode = frist;
        for (int i = 0; i < index; i++) {
            tempNode = tempNode.getNext();
        }
        return tempNode;
    }

    // 默认的获取情况 获取第一个
    public E get() {
        return get(0);
    }

    // 移除第一个元素
    public void removeFrist() {
        frist = frist.getNext();
        size--;
    }

    // 移除最后一个元素
    public void removeLast() {
        last = last.getPrevious();
        size--;
    }

    // 移除指定位置的元素
    public void remove(int index) {
        if (index == 0) {
            removeFrist();
            return;
        } else if (index == size - 1) {
            removeLast();
            return;
        }
        checkIndex(index);
        Node tempNode = getNode(index);
        Node previous = tempNode.getPrevious();
        Node next = tempNode.getNext();
        previous.setNext(next);
        next.setPrevious(previous);
        size--;

    }

    // 默认移除元素 移除第一个
    public void remove() {
        removeFrist();

    }

    // 清空容器
    public void clear() {
        frist = null;
        last = null;
        size = 0;
    }

    // 重写toString
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if (size == 0) {
            return sb.append(']').toString();
        }
        for (int i = 0; i < size; i++) {
            sb.append(get(i)).append(",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    // 返回有效的数据个数
    public int size() {
        return size;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

ps:纯属学习交流,若有错误欢迎纠错