LinkedList

title: 【学习之路】LinkedList封装
draft: true
tags:

• 学习之路
• Java
• 集合
  categories:
• JavaSE
• 集合
  cover: https://cdn.jsdelivr.net/gh/CodeZixuan/Blog_Images/91012893-6fa6e180-e619-11ea-9e98-9ceaf534d0ce.jpg
  abbrlink: 1910
  date: 2020-06-20 21:10:30

首先新建一个类为LinkedBox

创建静态一个内部类Node

定义三个属性，并且通过构造方法进行初始化

private static class Node{
    //首节点
    private Node<E> prev;
    //元素
    private E item;
    //尾结点
    private Node<E> next;
    public Node(Node<E> prev, E item, Node<E> next){
        this.prev = prev;
        this.item = item;
        this.next = next;
    }
}

在LinkedBox类中定义三个属性

public class LinkedBox<E>{
    //首节点
    private Node<E> first;
    //尾结点
    private Node<E> last;
    //有效元素个数
    private int size;
}

LinkedBox添加方法

public boolean add(E e){
    linklast(e);
    return true;
}
private void linklast(E e){
    Node<E> l = last;
    //l将尾结点给当前添加元素作为首节点
    //e为当前添加的元素
    //null表示添加在链表末尾,末尾没有元素先设置为空
    Node<E> newNode = new Node<E>(l, e, null);
    //当前链表的尾结点给last
    last = newNode;
      //判断尾结点是否为空,如果为空代表newNode就是首节点,当前元素也是首节点
    if (l == null)
        first = newNode;
    else
    //如果不是首节点,就把newNode给上一个元素的尾结点
        l.next = newNode;
    //有效元素个数加1
    size++;
}

LinkedBox删除方法

public E remove(int index){
    //开始方法前先判断index是否合法  
    indexException(index);
    return unlike(node(index));
}
//新建一个类定义一个异常
public class BoxIndexOutOfBoundsException extends RuntimeException{
    public BoxIndexOutOfBoundsException(){}
    public BoxIndexOutOfBoundsException(String msg){
        super(msg);
    }
}
//用来判断index是否越界
private void indexException(int index){
        if (index < 0 || index > size - 1){
            throw new BoxIndexOutOfBoundsException("Index:"+ index +",Size:"+ size);
        }
}
//用来查找index的位置
private Node<E> node(int index){
    //判断index是否小于size / 2如果小于从前面开始找index的值,不小于从后面找index的值
        if (index < (size >> 1)){
            Node<E> x = first;
            for (int i = 0; i < index; i++){
                x = x.next;
            }
            //返回当前对象
            return x;
        }else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--){
                x = x.prev;
            }
            //返回当前对象
            return x;
        }
}
//删除前后的node链接
private E unlink(Node<E> x){
        //先将查找到的node对象分别存储
        E elemet = x.item;
        Node Node<E> = x.prev;
        Node Node<E> = x.next;
        //判断当前对象首节点是否为空,如果为空那么代表删除的元素是第一个元素
        if (prev == null){
            //将下一个node对象给first
            first = next;
        }else {
            //把尾结点对象给上一个节点的尾结点
            prev.next = next;
            x.prev = null;
        }
        //判断当前对象是否为空,如果为空那么代表删除的元素是最后一个元素
        if (next == null){
               //将上一个对象node给last
            last = prev;
        }else {
            //把当前删除对象的首节点给下一个对象的首节点
            next.prev = prev;
            x.next = null;
        }
        x.item = null;//清空当前元素
        size--;//将有效元素个数减少一个
        return elemet;
}

LinkedBox修改方法

public boolean upDate(int index, E value){
    //先判断index是否合法
     indexException(index);
     node(index).item = value;
    return true;
}
//用node方法来查找元素
private Node<E> node(int index){
    //判断index是否小于size / 2如果小于从前面开始找index的值,不小于从后面找index的值
        if (index < (size >> 1)){
            Node<E> x = first;
            for (int i = 0; i < index; i++){
                x = x.next;
            }
            //返回当前对象
            return x;
        }else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--){
                x = x.prev;
            }
            //返回当前对象
            return x;
        }
}

LinkedBox查询方法

public E getElementDate(int index) {
        //先判断index是否合法
        indexException(index);
        return node(index).item;
    }
//调用node方法查询元素
private Node<E> node(int index){
    //判断index是否小于size / 2如果小于从前面开始找index的值,不小于从后面找index的值
        if (index < (size >> 1)){
            Node<E> x = first;
            for (int i = 0; i < index; i++){
                x = x.next;
            }
            //返回当前对象
            return x;
        }else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--){
                x = x.prev;
            }
            //返回当前对象
            return x;
        }
}