如何手写一个简单的LinkedList

淩亂°似流年 2022-05-12 12:36 238阅读 0赞

这是我写的第三个集合类了，也是简单的实现了一下基本功能，这次带来的是LinkedList的写法，需要注意的内容有以下几点：

1.LinkedList是由链表构成的，链表的核心即使data，前驱，后继

2.对于LinkedList不需要扩容操作，因此相对较为简单，但是在处理前驱，后继的时候需要注意一下

3.对于索引下标需要判断是否合法

4.对于一些头节点，尾节点的操作，需要注意判断，比如remove的时候，如果是删除头，中间，尾，方式都是不一样的

接下来来看代码，我的MyList接口：

public interface MyList {
    
        // 求容量
        int size();
    
        // 是否为空
        boolean isEmpty();
    
        // 判断是否存在
        boolean contains(Object o);
    
        // 清空集合
        void clear();
    
        // 返回添加是否成功
        boolean add(Object object);
    
        // 返回删除是否成功
        boolean remove(int index);
    
        // 获取索引位置的值
        Object get(int index);
    
    }

MyLinkedList实现类：

/**
     * @author kxm
     * @date 2018/9/17
     */
    public class MyLinkedList implements MyList {
    
        // 定义链表类,属性有，值，前驱，后驱
        class Node{
            Object obj;
            Node previous;
            Node next;
            public void setObj(Object obj) {
                this.obj = obj;
            }
            public void setPrevious(Node previous) {
                this.previous = previous;
            }
            public void setNext(Node next) {
                this.next = next;
            }
            public Node(Object obj, Node previous, Node next) {
                this.obj = obj;
                this.previous = previous;
                this.next = next;
            }
            public Node(){
            }
        }
        // LinkedList相应属性
        private Node first = null;
        private Node last = null;
        private int size = 0;
    
        // 返回集合长度
        @Override
        public int size() {
            return size;
        }
    
        // 返回集合是否为空
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public boolean contains(Object o) {
            for(int i = 0;i < size; i++){
                if(first != null){
                    o.equals(first.next.obj);
                    return true;
                }
            }
            return false;
        }
    
        @Override
        public void clear() {
            first.next = null;
            first.previous = null;
            last.next = null;
            last.previous = null;
            first.obj = null;
            last.obj = null;
            size = 0;
        }
    
        @Override
        public boolean add(Object object) {
            /*
             * 核心点！
             * 1.要对头结点判断是否为空，空的话将制定对象置为头结点
             * 2.重点：要将last置为结点
             * 3.size++
             */
            Node n = new Node();
            if(first == null){
                n.setPrevious(null);
                n.setObj(object);
                n.setNext(null);
                first = n;
                last = n;
            }else{
                n.setPrevious(last);
                n.setObj(object);
                n.setNext(null);
                last.setNext(n);
                last = n;
            }
            size++;
            return true;
        }
    
        /*
         * 要移除结点temp，先将temp的后继的前驱指向temp的前驱
         * 再将temp的前驱的后继指向temp的后继
         *
         * 重点，对于头和尾需要单独判断，不然会出现空指针异常
         */
        @Override
        public boolean remove(int index) {
            Node temp = node(index);
            if(temp==first || temp==last){
                if(temp == first){
                    temp.next.previous = null;
                    first = temp.next;
                }else if(temp == last){
                    temp.previous.next = null;
                    last = temp.previous;
                }
    
            }else{
                temp.next.previous = temp.previous;
                temp.previous.next = temp.next;
            }
            size--;
            return true;
        }
    
        // 通过链表遍历的方法实现get
        @Override
        public Object get(int index) {
            rangeCheck(index);
            Node temp = node(index);
            return temp.obj;
        }
    
        // 实现结点的遍历
        public Node node(int index){
            Node temp = null;
            if(first != null){
                temp = first;
            }
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
    
            return temp;
        }
    
        // 对索引下标进行合法性检查
        private void rangeCheck(int index){
            if(index < 0||index >= size){
                try {
                    throw new Exception();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }

测试代码截图：

![70][]

[70]: /images/20220512/7fa463506c9e47388abdea28917ee14b.png