线性表ArrayList和LinkedList源码详解。

你的名字 2022-05-16 08:18 196阅读 0赞

# List #

## 描述 ##

线性表抽象接口，所有线性表应该在实现这个接口的基础上进行操作。

## 接口 ##

package list;
    
    /**
     * Description: 线性表的接口，使用泛型保证类型
     *
     * @ClassName: List
     * @author 过道
     * @date 2018年8月13日 上午10:45:13
     */
    public interface ListInterface<T> {
        public void add(T newEntry);
    
        public void add(Integer newPosition, T newEntry);
    
        public T remove(int givePosition);
    
        public void clear();
    
        public T replace(int givenPosition, T newEntry);
    
        public T getEntry(int givenPosition);
    
        public T[] toArray();
    
        public boolean contains(T anEntry);
    
        public int getLength();
    
        public boolean isEmpty();
    }

# ArrayList #

1 接口

/**
     * 为了区分java默认的 ArrayList和我的list，所以命名为AList
     * 因为内部没有实现，所以很简单，就没有写注释
     */
    public class AList<T> implements ListInterface<T> {
        
    
        @Override
        public void add(T newEntry) {
            
        }
    
        @Override
        public void add(Integer newPosition, T newEntry) {
            
        }
    
        @Override
        public T remove(int givePosition) {
            return null;
        }
    
        @Override
        public void clear() {
            
        }
    
        @Override
        public T replace(int givenPosition, T newEntry) {
            return null;
        }
    
        @Override
        public T getEntry(int givenPosition) {
            return null;
        }
    
        @Override
        public T[] toArray() {
            return null;
        }
    
        @Override
        public boolean contains(T anEntry) {
            return false;
        }
    
        @Override
        public int getLength() {
            return 0;
        }
    
        @Override
        public boolean isEmpty() {
            return false;
        }
    
       
    }

## 2.实现途径 ##

Array的意思就是**数组**，所以很简单可以猜测到这是使用数组实现List，为了知道数组中多少个**有效位**，使用一个int值保存。初始化时，要么用户**给定数组容量**，要么使用**默认容量**。

> 注：强烈建议在使用ArrayList或其他扩容的容器时给定容量，因为这将大大节省扩容的时间。

public class AList<T> implements ListInterface<T> {
        //空数组，用来存放数据
        T[] list = null;
        // 当前有效的数字个数
        int numberOfEntries = 0;
        //如果用户不给定容量(强烈建议初始化时给定容量)， 默认的数组容量
        static final int DEFAULT_CAPACITY = 27;
    
        @SuppressWarnings("unchecked")
        public AList(int initialCapacity) {
            T[] tempList = (T[]) new Object[initialCapacity];
            list = tempList;
            numberOfEntries = 0;
        }
    
        public AList() {
            this(DEFAULT_CAPACITY);
        }
    
    // 其余覆盖的方法
    }

## 实现add方法 ##

注意一下，我们使用下标从1开始，所以不要与ArrayList混淆(从0开始)。

> 注：Vectory数组使用的是双倍扩容，即如果当前数组空间已满，我们申请双倍容量的数组，然后将原数组copy到新数组中.
> 
> ArrayList 中的数组使用的是1.5倍扩容，即申请 oldCapacity + (oldCapacity >> 1)---》意思是位运算除2，也就是新容量为1.5倍的旧容量。
> 
> 所以还是那句话，给定一个大致的容量，可以大幅度减少扩容的次数，优化速度.(大概只有像我这种新手才会默认容量吧)

@Override
        public void add(T newEntry) {
            // 与ArrayList 不同，我们选择下标从 1 开始。
            list[numberOfEntries + 1] = newEntry;
            numberOfEntries++;
            ensureCapacity();
            //也可以选择重用其他方法
    //        add(numberOfEntries+1,newEntry);
    // 这样重用，能有效减少代码，但是理解上稍微有些困难。并且增加了许多无谓的判断，降低了效率(当然这无所谓)
        }
    
        /**
         * 指定位置进行添加某一个数字
         *
         * @param newPosition
         * @param newEntry
         */
        @Override
        public void add(Integer newPosition, T newEntry) {
            if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
                if (newPosition <= numberOfEntries) {
                    makeRoom(newPosition);  // 将给定位置的数字及后续数字全部后移。
                }
                list[newPosition] = newEntry;
                numberOfEntries++;
                ensureCapacity();   // 为下次添加获取足够的空间
            } else {
                throw new IndexOutOfBoundsException("给定位置不合法，下标越界");
            }
        }
    
        /**
         * @param newPosition
         */
        private void makeRoom(Integer newPosition) {
            assert (newPosition >= 1) && (newPosition <= newPosition + 1);  //断言，如果不满足断言，则报错，需要手动开启assert
            int newIndex = newPosition;
            int lastIndex = numberOfEntries;
    
            for (int index = 0; index < newIndex; index++) {
                list[index + 1] = list[index];  //给定位置之后的数字全部后移一位，将给定位置‘空’下来
            }
        }
        /**
         * 倍扩容量
         */
        private void ensureCapacity() {
            int capacity = list.length - 1;
            if (numberOfEntries >= capacity) {
                int newCapacity = 2 * capacity;
                list = Arrays.copyOf(list, newCapacity + 1);
            }
        }

##  实现简单方法 ##

只要看懂了前面的底层实现，那么对于下面三个方法的实现应该不会有问题。

@Override
        public int getLength() {
            return numberOfEntries;
        }
    
        @Override
        public boolean isEmpty() {
            return numberOfEntries == 0;
        }
        @Override
        public void clear() {
            list = null;    //取消引用，等待GC回收
            numberOfEntries = 0;
        }

##  remove方法 ##

数组移除一个元素后，那么后续元素立刻跟进，弥补空隙。

> 注意：已经扩容后的容量不会被返还，也没有必要返还。

@Override
        public T remove(int givePosition) {
            if ((givePosition >= 1) && (givePosition <= numberOfEntries)) {
                assert !isEmpty();
                T result = list[givePosition];
                if (givePosition < numberOfEntries) {
                    removeGap(givePosition);    // 移除后出现空隙，我们让之后的元素前移一位，弥补空隙
                }
                return result;
            }
            return null;
        }
    
        /**
         * 给定位置为空隙，后续元素前进一位，补上空隙
         */
        private void removeGap(int givePosition) {
            assert (givePosition >= 1) && (givePosition < numberOfEntries);
            int removedIndex = givePosition;
            int lastIndex = numberOfEntries;
            for (int index = givePosition; index < lastIndex; index++) {
                list[index] = list[index + 1];
            }
        }

## toArray方法的实现 ##

> 注意：千万不要直接返回ArrayList底层的数组，我们应该新申请一个空间，并将元素逐个放入其中。如果返回list，将成为一个非常恐怖的事情。
> 
> 封装性：只要通过方法才能改变对象中的域。如果把数组直接返回，那么客户端程序员可以随意更改对象的域。

@Override
        public T[] toArray() {
            /* 这里千万不能返回我们使用的T[] list
             * 因为用户可能会对返回数组进行修改，
             * 如果返回list,那么封装失败。
             * 也就是说用户可以不使用我们提供的方法进行操作List，这是很恐怖的事情。
             */
            T[] result = (T[]) new Object[numberOfEntries];
            for (int index = 0; index < numberOfEntries; index++) {
                result[index] = list[index + 1];
            }
            return result;
        }

##  其余方法 ##

@Override
        public T replace(int givenPosition, T newEntry) {
            if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
                assert !isEmpty();
                T oldEntry = list[givenPosition];
                list[givenPosition] = newEntry;
                return oldEntry;
            }
            //省去报错的部分
            return null;
        }
    
        @Override
        public T getEntry(int givenPosition) {
            // 判断给定位置是否合法，不合法就报错。
            if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
                assert !isEmpty();
                return list[givenPosition];
            }
            //else就报错，我省去此步
            return null;
        }
    
        
    
        @Override
        public boolean contains(T anEntry) {
            boolean found = false;
            int index = 1;
            // 遍历寻找，找到一个就结束循环。
            while (!found && (index <= numberOfEntries)) {
                if (anEntry.equals(list[index])) {
                    found = true;
                }
                index++;
            }
            return found;
        }

##  全部方法实现源码 ##

package list;
    
    
    import java.util.Arrays;
    
    /**
     * 为了区分java默认的 ArrayList和我的list，所以命名为ArrayList
     */
    public class AList<T> implements ListInterface<T> {
        T[] list = null;
        int numberOfEntries = 0;
        static final int DEFAULT_CAPACITY = 27;
    
        @SuppressWarnings("unchecked")
        public AList(int initialCapacity) {
            T[] tempList = (T[]) new Object[initialCapacity];
            list = tempList;
            numberOfEntries = 0;
        }
    
        public AList() {
            this(DEFAULT_CAPACITY);
        }
    
        @Override
        public void add(T newEntry) {
            // 与ArrayList 不同，我们选择下标从 1 开始。
            list[numberOfEntries + 1] = newEntry;
            numberOfEntries++;
            ensureCapacity();
            //也可以选择重用其他方法
    //        add(numberOfEntries+1,newEntry);
    // 这样重用，能有效减少代码，但是理解上稍微有些困难。并且增加了许多无谓的判断，降低了效率(当然这无所谓)
        }
    
        /**
         * 指定位置进行添加某一个数字
         *
         * @param newPosition
         * @param newEntry
         */
        @Override
        public void add(Integer newPosition, T newEntry) {
            if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
                if (newPosition <= numberOfEntries) {
                    makeRoom(newPosition);  // 将给定位置的数字及后续数字全部后移。
                }
                list[newPosition] = newEntry;
                numberOfEntries++;
                ensureCapacity();   // 为下次添加获取足够的空间
            } else {
                throw new IndexOutOfBoundsException("给定位置不合法，下标越界");
            }
        }
    
        /**
         * @param newPosition
         */
        private void makeRoom(Integer newPosition) {
            assert (newPosition >= 1) && (newPosition <= newPosition + 1);  //断言，如果不满足断言，则报错，需要手动开启assert
            int newIndex = newPosition;
            int lastIndex = numberOfEntries;
    
            for (int index = 0; index < newIndex; index++) {
                list[index + 1] = list[index];  //给定位置之后的数字全部后移一位，将给定位置‘空’下来
            }
        }
    
        @Override
        public T remove(int givePosition) {
            if ((givePosition >= 1) && (givePosition <= numberOfEntries)) {
                assert !isEmpty();
                T result = list[givePosition];
                if (givePosition < numberOfEntries) {
                    removeGap(givePosition);    // 移除后出现空隙，我们让之后的元素前移一位，弥补空隙
                }
                return result;
            }
            return null;
        }
    
        /**
         * 给定位置为空隙，进行弥补空隙，
         *
         * @param givePosition
         */
        private void removeGap(int givePosition) {
            assert (givePosition >= 1) && (givePosition < numberOfEntries);
            int removedIndex = givePosition;
            int lastIndex = numberOfEntries;
            for (int index = givePosition; index < lastIndex; index++) {
                list[index] = list[index + 1];
            }
        }
    
        @Override
        public void clear() {
            list = null;    //取消引用，等待GC回收
            numberOfEntries = 0;
        }
    
        @Override
        public T replace(int givenPosition, T newEntry) {
            if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
                assert !isEmpty();
                T oldEntry = list[givenPosition];
                list[givenPosition] = newEntry;
                return oldEntry;
            }
            return null;
        }
    
        @Override
        public T getEntry(int givenPosition) {
            if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
                assert !isEmpty();
                return list[givenPosition];
            }
            //else就报错，我省去此步
            return null;
        }
    
        @Override
        public T[] toArray() {
            T[] result = (T[]) new Object[numberOfEntries];
            for (int index = 0; index < numberOfEntries; index++) {
                result[index] = list[index + 1];
            }
            return result;
        }
    
        @Override
        public boolean contains(T anEntry) {
            boolean found = false;
            int index = 1;
            while (!found && (index <= numberOfEntries)) {
                if (anEntry.equals(list[index])) {
                    found = true;
                }
                index++;
            }
            return found;
        }
    
    
        @Override
        public int getLength() {
            return numberOfEntries;
        }
    
        @Override
        public boolean isEmpty() {
            return numberOfEntries == 0;
        }
    
        /**
         * 倍扩容量
         */
        private void ensureCapacity() {
            int capacity = list.length - 1;
            if (numberOfEntries >= capacity) {
                int newCapacity = 2 * capacity;
                list = Arrays.copyOf(list, newCapacity + 1);
            }
        }
    }

##  总结 ##

如果说ArrayList 需要注意的地方

1.  1.5倍扩容，思想很棒，但是比较浪费时间，所以程序员尽可能估算要使用的空间的大概上界，然后初始化时给定容量。
2.  toArray时，尽管底层有数组，但是千万不能返回底层的数组。
3.  clear时，直接将数组引用置为null，GC就可以回收到这块内存了。

顺带说几句：双倍扩容是Vector使用的方法，ArrayList使用的是1.5倍扩容，并且vector的方法实现了线程安全，但是ArrayLust没有，所以在不要求线程安全的情况下使用ArrayList，能加快代码的运行速度。

# LinkedList #

## 实现接口 ##

package list;
    
    /**
     * 为了区分LinkedList，所以命名为LList，但本质都是双向链表
     * 下标从 1 开始，与java源码不同（以0开始）
     */
    public class LList<T> implements ListInterface<T> {
        
    
        @Override
        public void add(T newEntry) {
            
        }
    
        @Override
        public void add(Integer newPosition, T newEntry) {
            
        }
    
        @Override
        public T remove(int givePosition) {
            return null;
        }
    
        @Override
        public void clear() {
            size = 0;
            first = null;
        }
    
        @Override
        public T replace(int givenPosition, T newEntry) {
            return null;
        }
    
        @Override
        public T getEntry(int givenPosition) {
            return null;
        }
    
        @Override
        public T[] toArray() {
            return null;
        }
    
        @Override
        public boolean contains(T anEntry) {
            return false;
        }
    
        @Override
        public int getLength() {
            return 0;
        }
    
        @Override
        public boolean isEmpty() {
            return false;
        }
    
       
    }

## 底层实现 ##

明显使用链式，所以我们需要定义结点类Node。

其次，我们刚开始使用单向链表，利于实现与理解，之后会修改部分代码使其成了双向链表。并提供一些双向链表特有的操作。

public class LList<T> implements ListInterface<T> {
        int size;
        Node firstNode;
        
        // 链式实现无法给定容量，所以一个无参构造即可。
        public LList() {
            size = 0;
            firstNode = null;
        }
    
        //省去覆盖方法
    
        // 单向结点，只需要next和data就足够了
        class Node {
            T data;
            Node next;
    
            public Node() {
            }
    
            public Node(T data) {
                this(data, null);
            }
    
            public Node(T data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    }

## 核心方法:add的实现 ##

@Override
        public void add(T newEntry) {
            // 尾部位置进行添加
            add(size, newEntry);
        }
    
        @Override
        public void add(Integer newPosition, T newEntry) {
            Node newNode = new Node(newEntry);
            if (newPosition == 1) {
                //头结点插入
                newNode.next = firstNode;
                firstNode = newNode;
            } else if (newPosition > 1 && newPosition <= size) {
                Node beforeNode = firstNode;
                int count = 1;
                // 找到链表对应位置的前一位，进行插入操作
                while (count != newPosition - 1) {
                    beforeNode = beforeNode.next;
                    count++;
                }
                // 插入元素
                newNode.next = beforeNode.next;    // 链接起来了
                beforeNode.next = newNode;
            } else {
                throw new IndexOutOfBoundsException("给定位置越界");
            }
        }

## LinkedList全部源码 ##

package list;
    
    /**
     * 为了区分LinkedList，所以命名为LList，但本质都是双向链表
     * 下标从 1 开始，与java源码不同（以0开始）
     */
    public class LList<T> implements ListInterface<T> {
        private int size;
        private Node firstNode;
    
        public LList() {
            size = 0;
            firstNode = null;
        }
    
        @Override
        public void add(T newEntry) {
            // 尾部位置进行添加
            add(size, newEntry);
        }
    
        @Override
        public void add(Integer newPosition, T newEntry) {
            Node newNode = new Node(newEntry);
            if (newPosition == 1) {
                //头结点插入
                newNode.next = firstNode;
                firstNode = newNode;
            } else if (newPosition > 1 && newPosition <= size) {
                Node beforeNode = firstNode;
                int count = 1;
                // 找到链表对应位置的前一位，进行插入操作
                while (count != newPosition - 1) {
                    beforeNode = beforeNode.next;
                    count++;
                }
                // 插入元素
                newNode.next = beforeNode.next;    // 链接起来了
                beforeNode.next = newNode;
            } else {
                throw new IndexOutOfBoundsException("给定位置越界");
            }
        }
    
        @Override
        public T remove(int givePosition) {
            T result;
            if ((givePosition >= 1) && (givePosition <= size)) {
                assert !isEmpty();
                if (givePosition == 1) {
                    // 头结点的移除
                    result = firstNode.data;
                    firstNode = firstNode.next;
                } else {
                    Node nodeBefore = getNodeAt(givePosition - 1);
                    Node nodeToRemove = nodeBefore.next;
                    result = nodeBefore.data;
                    Node nodeAfter = nodeToRemove.next;
                    nodeBefore.next = nodeAfter;    // 断开移除结点的两侧
                }
                size--;
                return result;
            } else
                throw new IndexOutOfBoundsException("下标越界");
        }
    
        private Node getNodeAt(int i) {
            if (i > 0 && i <= size) {
                Node curNode = firstNode;
                for (int j = 0; j < i; j++)
                    curNode = curNode.next;
                return curNode;
            } else
                throw new IndexOutOfBoundsException("下标越界");
        }
    
        @Override
        public void clear() {
            size = 0;
            firstNode = null;
        }
    
        @Override
        public T replace(int givenPosition, T newEntry) {
            // 判断和报错都交给 getNodeAt 方法去做
            Node nodeToReplace = getNodeAt(givenPosition);
            T result = nodeToReplace.data;
            nodeToReplace.data = newEntry;
            return result;
        }
    
        @Override
        public T getEntry(int givenPosition) {
    
            return getNodeAt(givenPosition).data;
        }
    
        @Override
        public T[] toArray() {
            T[] result = (T[]) new Object[size];
            Node curNode = firstNode;
            for (int i = 0; i < size; i++) {
                result[i] = curNode.data;
            }
            return null;
        }
    
        @Override
        public boolean contains(T anEntry) {
            Node curNode = firstNode;
            boolean found = false;
            while (!found && curNode != null) {
                if (curNode.data.equals(anEntry)) {
                    found = true;
                }
                curNode = curNode.next;
            }
            return found;
        }
    
        @Override
        public int getLength() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            boolean result = false;
            // 为了提供更多的报错信息，在这里使用断言，需要手动开启断言功能。且程序开发中不建议使用。
            if (size == 0) {
                assert firstNode == null;
                result = true;
            } else {
                assert firstNode != null;
                result = false;
            }
            return result;
        }
    
        class Node {
            T data;
            Node next;
    
            public Node() {
            }
    
            public Node(T data) {
                this(data, null);
            }
    
            public Node(T data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    }

接下来只需要把单向链表改成双向链表即可，增加几个“getPrevNode()，addFirstNode()”之类的方法，修改add()，即可。