Preface

This chapter explains the underlying implementation of ArrayList, a sequential storage structure

Method

1. Concept

We know that the chain storage structure of linear list is implemented in Java by LinkedList. So we've been using LinkedList for so long. If we don't know how funny the underlying implementation of LinkedList is, let's unveil its mystery.

2. Realization Ideas

1) Build our own List interface

We can try to write the most basic Abstract method. For example, the method of finding the number of elements in a set, etc.

package cn.edu.ccut;
/**
 * Imitate List Interface
 * @author wangjian
 *
 * @param <E>
 */
public interface List<E> {
	
	public int size();//Get the collection length
	
	public boolean add(E e);//New Objects
	
	public E get(int index);//Obtain objects
	
	public E remove(int index);//delete object
	
	public boolean isEmpty();//Judging whether a set is empty
	
	public int indexOf(Object obj);//Determine the location of elements in a set
	
	public boolean contains(Object obj);//Determine whether an element is in a set
}

2) Write a concrete implementation class LinkedList

package cn.edu.ccut;

public class LinkedList<E> implements List<E> {

	private int size;
	
	private Node<E> first;//The first node of the current list
	
	private Node<E> last;//The last node of the current list
	
	//Define static inner classes of nodes
	private static class Node<E> {
        E item; //data object
        Node<E> next;//Next node
        Node<E> prev;//The former node

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
	
	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean add(E e) {
		Node<E> l = last;//Get the last node
		Node<E> newNode = new Node<>(l, e, null);//New nodes to be added
		last = newNode;
		if(l == null){//no data
			first = newNode;
		}else {
			l.next = newNode;//Hand in Hand with the Last Node
		}
		size++;
		return true;
	}
	
	private void checkIndexOfLink(int index){
		if( index < 0 || index > size-1){
			String error = "index: "+index+",size: "+size;
			throw new ArrayIndexOutOfBoundsException(error);
		}
	}

	@Override
	public E get(int index) {
		checkIndexOfLink(index);
		Node<E> currentNode = first;
		for (int i = 0; i < index; i++) {
			currentNode = currentNode.next;
		}
		return currentNode.item;
	}

	@Override
	public E remove(int index) {
		checkIndexOfLink(index);
		//Get the node to delete
		Node<E> currentNode = first;
		for (int i = 0; i < index; i++) {
			currentNode = currentNode.next;
		}
		Node<E> currentPre = currentNode.prev;//The precursor of the current node
		Node<E> currentNext = currentNode.next;//Succession of the current node
		E currentItem = currentNode.item;//Current node value
		if(currentPre == null){
			first = currentNext;//Delete the first element without holding hands
		}else {
			currentPre.next = currentNext;//Handle
			currentNode.prev = null;//Let go
		}
		if(currentNext == null){
			last = currentPre;//Deleting the last element without holding hands
		}else {
			currentNext.prev = currentPre;//Handle
			currentNode.next = null;//Let go
		}
		currentNode.item = null;//Data blanking
		size--;
		return currentItem;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public int indexOf(Object obj) {
		int index = 0;
        if (obj == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (obj.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
	}

	@Override
	public boolean contains(Object obj) {
		return indexOf(obj) >= 0;
	}

}

Please carefully understand the implementation details of the code.