模拟实现ArrayList与 LinkedList

今天药忘吃喽~ 2022-06-02 01:19 320阅读 0赞

可参考文章：[ArrayList 与 LinkedList 底层实现分析][ArrayList _ LinkedList]

我们知道ArrayList 底层使用数组实现的，了解ArrayList 的实现原理之后，我们就可以通过代码去简单模拟实现其中的过程。

public class MyArrayList {
    
        Object [] elementDate = new Object[4];
        //数组中包含的非null 数据的大小
        public int size = 0;
    
        public void add(Object value){
            //当数组长度不够时进行扩容，长度为原数组非null 容量的两倍
            if(size >= elementDate.length){
                //完成数组的拷贝，实现扩容
                Object[] temp = new Object[size * 2];
                for(int i = 0; i< elementDate.length; i++)
                    temp[i] = elementDate[i];
                elementDate = temp;
            }
    
            elementDate[size] = value;
            size ++;
        }
    
        //在操作集合时进行下标检查
        public void rangeCheck(int index){
            if(index >= size || index < 0)
                throw new IndexOutOfBoundsException("下标越界");
        }
    
        public Object get(int index){
            rangeCheck(index);
            return elementDate[index];
        }
    
        public void set(int index,Object value){
            rangeCheck(index);
            elementDate[index] = value;
        }
    
    
        public void clear(){
            //将数据清空，执行GC，释放内存，增加效率
            for (int i = 0; i < size; i++)
                elementDate[i] = null;
    
            size = 0;
        }
    
        public void remove(int index){
            rangeCheck(index);
            //以传入的下标为基准，将后面的所有数据向前移动一个单位
            for(int i=index; i<size; i++)
                elementDate[i] = elementDate[i+1];
    
            elementDate[size--] = null;
        }
    
    
        @Test
        public void testMyArrayList(){
            MyArrayList arrayList = new MyArrayList();
            for(int i=0; i<10; i++)
                arrayList.add(i);
    
            arrayList.remove(0);
            arrayList.set(0,100);
            for (int i=0; i<arrayList.size; i++)
                System.out.print(arrayList.get(i) + " ");
    
            System.out.println();
    
            arrayList.clear();
            System.out.println(arrayList.size);
    
        }
    }

> 输出  
> 100 2 3 4 5 6 7 8 9  
> 0

通过单向链表模拟实现LinkedList，这里使用了单向链表简单实现了LinkedList 的一些方法。PS ：LinkedList 底层使用了双向链表。

import org.junit.Test;
    
    public class MyLinkedList {
    
        //头结点
        public Node head = null;
        //链表元素个数
        public int size = 0;
    
        public void add(Object value){
            Node node = new Node(value);
    
            if(head == null){
                head = node;
            }else{
                Node temp = head;
                while(temp.getNext() != null){
                    temp = temp.getNext();
                }
                temp.setNext(node);
            }
            size ++;
        }
    
        //下标检查
        public void checkElementIndex(int index){
            if(index >= size || index < 0)
                throw new IndexOutOfBoundsException("下标越界");
        }
    
        public Object get(int index){
            checkElementIndex(index);
    
            //根据头结点找到当前节点，返回节点值
            Node temp = head;
            for(int i=0; i<index; i++){
                temp = temp.getNext();
            }
            return temp.getValue();
        }
    
        public void set(int index,Object value){
            checkElementIndex(index);
    
            //根据头结点找到当前节点，设置当前节点值
            Node temp = head;
            for(int i=0; i<index; i++){
                temp = temp.getNext();
            }
    
            temp.setValue(value);
        }
    
        //只需要让头结点为null 由于后续节点再无引用，会被GC 收集，因此效率很高
        public void clear(){
            head = null;
            size = 0;
        }
    
        public void remove(int index){
            checkElementIndex(index);
    
            //如果是头结点，让头结点变成头结点后的一个节点
            if(index == 0){
                head = head.getNext();
            }else{
                Node temp = head;
                //找到删除元素节点的前一个节点，改变其后继节点
                for(int i=0; i<index - 1; i++){
                    temp = temp.getNext();
                }
                temp.setNext(temp.getNext().getNext());
            }
    
            size --;
        }
    
        //内部类，模拟单向链表，保存元素值与下一个节点
        private static class Node{
            private Object value;
            private Node next;
    
            Node(Object value){
                this.value = value;
            }
    
            public Object getValue() {
                return value;
            }
            public void setValue(Object value) {
                this.value = value;
            }
            public Node getNext() {
                return next;
            }
            public void setNext(Node next) {
                this.next = next;
            }
        }
    
        @Test
        public void testMyLinkedList(){
            MyLinkedList linkedList = new MyLinkedList();
    
            for(int i=0; i<10; i++)
                linkedList.add(i);
    
            linkedList.remove(0);
            linkedList.set(0,100);
            for (int i=0; i<linkedList.size; i++)
                System.out.print(linkedList.get(i) + " ");
            System.out.println();
    
            linkedList.clear();
            System.out.println(linkedList.size);
        }
    }

> 输出  
> 100 2 3 4 5 6 7 8 9  
> 0

这里只是运用其中的思想简单的模拟实现了ArrayList 与LinkedList ，源码中的ArrayList 与LinkedList 实现要比这复杂的多。如果小伙伴们有兴趣可以去查看底层的实现源码，想必一定会有收获。

[ArrayList _ LinkedList]: http://blog.csdn.net/codejas/article/details/78768340