模拟ArrayList、LinkedList底层实现

布满荆棘的人生 2024-02-18 21:02 41阅读 0赞

1、MyList接口：

package shixian;
    
    public interface MyList<E> extends Iterable<E> {
        /**添加一个新元素在list末尾*/
    	public void add(E e);
    	/**添加一个新元素在指定的索引处*/
    	public void add(int index,E e);
    	/**clear the list*/
    	public void clear();
    	/**是否包含某个指定元素*/
    	public boolean contains(E e);
    	/**返回指定的索引元素*/
    	public E get(int index);
    	/**获取第一次匹配时的索引，否则return -1*/
    	public int indexOf(E e);
    	/**判断list是否为空*/
    	public boolean isEmpty();
    	/**返回最后匹配元素索引，未找到返回-1*/
    	public int lastIndexOf(E e);
    	/**移除list中第一次出现的匹配元素，成功返回true*/
    	public boolean remove(E e);
    	/**移除指定位置元素，移除成功返回移除的元素*/
    	public E remove(int index);
    	/**设置指定位置元素,返回旧元素*/
    	public E set(int index,E e);
    	/**返回list大小*/
    	public int size();
    }

`2、抽象接口MyAbstractList实现部分MyList接口方法：`

package shixian;
    
    public abstract class MyAbstractList<E> implements MyList<E>{
        protected int size = 0; //元素个数
        
        protected MyAbstractList() {
        	
        }
        
        protected MyAbstractList(E[] objects) {
    		for(int i = 0; i < objects.length; i++)
    			add(objects[i]);
    	}
        
        /**在list末尾添加新元素*/
        @Override
        public void add(E e) {
        	add(size, e);
        }
        
        /**list是否不包含元素*/
        @Override
        public boolean isEmpty() {
        	return size == 0;
        }
        
        /**删除首次匹配元素*/
        public boolean remove(E e) {
          if(indexOf(e) >= 0) {
        	  remove(indexOf(e));
        	  return true;
          }
          else 
        	  return false;
        }
        
        /**返回元素个数*/
    	@Override
    	public int size() {
    		return size;
    	}    
    }

3、MyArrayList继承抽象接口：

package shixian;
    
    import java.util.Iterator;
    //底层通过数组实现
    public class MyArrayList<E> extends MyAbstractList<E>{
        public static final int INITIAL_CAPACITY = 16;  //初始大小
       
    	private E[] data = (E[]) new Object[INITIAL_CAPACITY];
    	
        public MyArrayList() {
    		// TODO Auto-generated constructor stub
        }
        
        public MyArrayList(E[] objects) {
        	for(int i = 0; i < objects.length; i++) {
        		add(objects[i]);
        	}
        }
       
       /**指定位置添加元素*/
        @Override
    	public void add(int index, E e) {
    		ensureCapacity();
    		
    		for(int i = size - 1; i >= index; i--)
              data[i+1] = data[i];
    		
    		data[index] = e;
    		size++;
    	}
    
        /**如果数组存满元素， 则另外创建大小为原数组两倍+1的数组*/
        private void ensureCapacity() {
        	if(size >= data.length) {
        		E[] newData = (E[]) new Object[size * 2 + 1];
        		System.arraycopy(data, 0, newData, 0, size);
        		data = newData;
        	}
        }
        
        /**clear the list*/
    	@Override
    	public void clear() {
    		data = (E[]) new Object[INITIAL_CAPACITY];
    		size = 0;
    	}
    
    	@Override
    	public boolean contains(E e) {
    		for(int i = 0; i < size; i++)
    			if(e.equals(data[i])) return true;
    		return false;
    	}
    
    	@Override
    	public E get(int index) {
    		checkIndex(index);
     		return data[index];
    	}
    
    	private void checkIndex(int index) {
    		if(index < 0 || index >= size)
    			throw new IndexOutOfBoundsException
    			 ("index " + index + " out of bounds");
    	}
    	
    	@Override
    	public int indexOf(E e) {
    		for(int i = 0; i < size; i++)
    			if(e.equals(data[i])) return i;
    		return -1;
    	}
    
    	@Override
    	public int lastIndexOf(E e) {
    		for(int i = size - 1; i >= 0; i--)
    			if(e.equals(data[i])) return i;
    		return -1;
    	}
    
    	@Override
    	public E remove(int index) {
    		checkIndex(index);
    		
    		E e = data[index];
    		
    		for(int j = index; j < size -1; j++)
    			data[j] = data[j + 1];
    		data[size -1] = null;
    		
    		size--;
    		return e;
    	}
    
    	@Override
    	public E set(int index, E e) {
    		checkIndex(index);
    		E old = data[index];
    		data[index] = e;
    		return old;
    	}
    
    	@Override
    	public String toString() {
    		StringBuilder result = new StringBuilder("[");
    		
    		for(int i = 0; i < size; i++) {
    			result.append(data[i]);
    			if(i < size - 1) result.append(", ");
    		}
    		
    		return result.toString() + "]";
    	}
    	
    	/**改变当前capacity大小为当前size大小*/
    	public void trimToSize() {
    		if(size != data.length) {
    			E[] newData = (E[]) new Object[size];
    			System.arraycopy(data, 0, newData, 0, size);
    			data  = newData;
    		}
    	}
    	
    	/**返回迭代器*/
    	@Override
    	public Iterator<E> iterator() {
    		return new ArrayListIterator();
    	}
    
    	private class ArrayListIterator implements java.util.Iterator<E>{
            private int current = 0;//current index
            
    		@Override
    		public boolean hasNext() {
    			return current < size;
    		}
    
    		@Override
    		public E next() {
    			return data[current++];
    		}
    
    		@Override
    		public void remove() {
    			MyArrayList.this.remove(current);
    		}
    		
    	}
    }

4、MyArrayList测试：

package shixian;
    
    public class TestMyArrayList {
    
    	public static void main(String[] args) {
    	   MyList<String> list = new MyArrayList<>();
    	   list.add("America");
    	   System.out.println("(1) " + list);
    
    	   list.add(0,"Canada");
    	   System.out.println("(2) " + list);
    	   
    	   list.add("Russia");
    	   System.out.println("(3) " + list);
    	   
    	   list.add("France");
    	   System.out.println("(4) " + list);
    	   
    	   list.add(2,"Germany");
    	   System.out.println("(5) " + list);
    
    	   list.add(5,"Norway");
    	   System.out.println("(6) " + list);	   
    	   
    	   list.remove("Canada");
    	   System.out.println("(7) " + list);
    	   
    	   list.remove(2);
    	   System.out.println("(8) " + list);
    	   
    	   list.remove(list.size() - 1);
    	   System.out.println("(9) " + list);
    	   
    	   for (String s : list) {
    		   System.out.print(s.toUpperCase() + " ");
    		
    	}
    	}
    
    }
    
    /**
     * 
    (1) [America]
    (2) [Canada, America]
    (3) [Canada, America, Russia]
    (4) [Canada, America, Russia, France]
    (5) [Canada, America, Germany, Russia, France]
    (6) [Canada, America, Germany, Russia, France, Norway]
    (7) [America, Germany, Russia, France, Norway]
    (8) [America, Germany, France, Norway]
    (9) [America, Germany, France]
    AMERICA GERMANY FRANCE 
     * */

\----------------------------------------------------------------------------------------

LinkedList底层实现：

package shixian;
    
    import java.util.Iterator;
    
    public class MyLinkedList<E> extends MyAbstractList<E>{
        private Node<E> head,tail;
        
        /**无参构造函数*/
        public MyLinkedList() {
    		// TODO Auto-generated constructor stub
    	}
        
        /**带参构造函数*/
        public MyLinkedList(E[] objects) {
        	super(objects);
        }
        
        /**获取第一个元素*/
        public E getFirst() {
        	if(size == 0) {
        		return null;
        	}else {
        		return head.element;
        	}
        }
        
        /**获取最后一个元素*/
        public E getLast() {
        	if(size == 0) {
        		return null;
        	} else {
    			return tail.element;
    		}
        }
        
        /**添加第一个元素*/
        public void addFirst(E e) {
        	Node<E> newNode = new Node<>(e);
        	newNode.next = head;
        	head = newNode;
        	size++;
        	
        	if(tail == null) {
        		tail = head;
        	}
        }
        
        /**末尾添加元素*/
        public void addLast(E e) {
        	Node<E> newNode = new Node<>(e);
        	
        	if(tail == null) {
        		head = tail = newNode;
        	}
        	else {
        		tail.next = newNode;
        		tail = tail.next;
        	}
        	
        	size++;
        }
        
        /**移除第一个元素，并返回移除元素*/
        public E removeFirst() {
        	if(size == 0) return null;
        	else {
        		Node<E> temp = head;
        		head = head.next;
        		size--;
        		if(head == null) tail = null;
        		return temp.element;
        	}
        }
        
        /**移除最后一个元素，并返回移除元素*/
        public E removeLast() {
        	if(size == 0) return null;
        	else if(size == 1) {
        		Node<E> temp = head;
        		head = tail = null;
        		size = 0;
        		return temp.element;
        	}
        	else {
        		Node<E> current = head;
        		for(int i = 0; i < size - 2; i++)
        			current = current.next;
        		
        		Node<E> temp = tail;
        		tail = current;
        		tail.next = null;
        		size--;
        		return temp.element;
        	}
        }
        
        /**指定位置添加元素*/
    	@Override
    	public void add(int index, E e) {
    		if(index == 0) addFirst(e);
    		else if(index >= size) addLast(e);
    		else {
    			Node<E> current = head;
    			for(int i = 1; i < index; i++)
    				current = current.next;
    			Node<E> temp = current.next;
    			current.next = new Node<>(e);
    			(current.next).next = temp;
    			size++;
    		}
    	}
    
    	/**clear the list*/
    	@Override
    	public void clear() {
    		size = 0;
    		head = tail = null;
    	}
    
    	/**重写toString方法*/
    	@Override
    	public String toString() {
    		StringBuilder result = new StringBuilder("[");
    		
    		Node<E> current = head;
    		for(int i = 0; i < size; i++) {
    			result.append(current.element);
    			current = current.next;
    			if(current != null) {
    				result.append(", ");
    			}else {
    				result.append("]");
    			}
    		}
    		return result.toString();
    	}
    	
    	
    	
    	@Override
    	public boolean contains(E e) {
    		if(size == 0) return false;
    		else {
    			Node<E> current = head;
    			for(int i = 0; i < size; i++) {
    				if(current.element.equals(e)) {
    					return true;
    				}
    				current = current.next;
    			}
    		}
    		return false;
    	}
    
    	@Override
    	public E get(int index) {
    		if(index < 0 || index >= size) return null;
    		else {
    			Node<E> current = head;
    			for(int i = 0; i < size ; i++) {
    				if(index == i) {
    					return current.element;
    				}
    				current = current.next;
    			}
    		}
    		return null;
    	}
    
    	/**返回第一个匹配元素下标*/
    	@Override
    	public int indexOf(E e) {
    		Node<E> current = head;
    		for(int i = 0; i < size; i++) {
    			if(current.element.equals(e)) {
    				return i;
    			}
    			current = current.next;
    		}
    		return -1;
    	}
    
    	/**返回最后匹配元素下标*/
    	@Override
    	public int lastIndexOf(E e) {
    		Node<E> current = head;
    		int temp = -1;
    		for(int i = 0; i < size; i++) {
    			if(current.element.equals(e)) {
    				temp = i;
    			}
    			current = current.next;
    		}
    		return temp;
    	}
    
    	/**移除指定位置元素，并返回删除元素*/
    	@Override
    	public E remove(int index) {
    		if(index < 0 || index >= size) return null;
    		else if(index == 0) return removeFirst();
    		else if(index == size -1) return removeLast();
    		else {
    			Node<E> previous = head;
    			for(int i = 1; i < index; i++)
    				previous = previous.next;
    			
    			Node<E> current = previous.next;
    			previous.next = current.next;
    			size--;
    			return current.element;
    		}
    	}
    
    	/**设置指定下标元素，并返回旧元素*/
    	@Override
    	public E set(int index, E e) {
    		Node<E> current = head;
    		E temp = null;
    		for(int i = 0; i < size;i++) {
    			if(i == index) {
    				temp = current.element;
    				current.element = e;
    			}
    			current = current.next;
    		}
    		return temp;
    	}
    
    	@Override
    	public Iterator<E> iterator() {
    		return new LinkedListIterator();
    	}
    
    	/**实现迭代器，遍历list容器*/
    	private class LinkedListIterator implements java.util.Iterator<E>{
            private Node<E> current = head;
            
    		@Override
    		public boolean hasNext() {
    			return (current != null);
    		}
    
    		@Override
    		public E next() {
    			E e = current.element;
    			current = current.next;
    			return e;
    		}
    
    		@Override
    		public void remove() {
    			MyLinkedList.this.remove(current.element);
    		}
    		
    	}
    	
    	/**
    	 * 该类只用于LinkList中，故为private
    	 * 该类不需要任何LinkList的实例访问，故为static
    	 * */
    	private static class Node<E> {
    	    E element;
    	    Node<E> next;
    	    
    	    public Node(E e) {
    	    	element = e;
    	    }		
    	}
    }

测试：

package shixian;
    
    public class TestMyLinkedList {
    
    	public static void main(String[] args) {
    		MyLinkedList<String> list = new MyLinkedList<>();
    		
    		list.add("America");
    		System.out.println("(1) "+list);
    
    		list.add(0,"Canada");
    		System.out.println("(2) "+list);
    		
    		list.add("Russia");
    		System.out.println("(3) "+list);
    		
    		list.addLast("France");
    		System.out.println("(4) "+list);
    		
    		list.add(2,"Germany");
    		System.out.println("(5) "+list);
    		
    		list.add(5,"Norway");
    		System.out.println("(6) "+list);
    		
    		list.addFirst("Poland");
    		System.out.println("(7) "+list);
    		
    		list.remove(0);
    		System.out.println("(8) "+list);
    		
    		list.remove(2);
    		System.out.println("(9) "+list);
    		
    		list.remove(list.size() - 1);
    		System.out.print("(10) "+list + "\n(11) ");
    		
    		for (String s : list) {
    			System.out.print(s.toUpperCase() + " ");
    		}
    		
    		System.out.println();
    		System.out.println("(12) is contains Russia ? " + list.contains("Russia"));
    		System.out.println("(13) get(0) : "+list.get(0));
    		System.out.println("(14) lastIndexOf : "+list.lastIndexOf("Russia"));
    	}
    
    }
    
    
    /**
    (1) [America]
    (2) [Canada, America]
    (3) [Canada, America, Russia]
    (4) [Canada, America, Russia, France]
    (5) [Canada, America, Germany, Russia, France]
    (6) [Canada, America, Germany, Russia, France, Norway]
    (7) [Poland, Canada, America, Germany, Russia, France, Norway]
    (8) [Canada, America, Germany, Russia, France, Norway]
    (9) [Canada, America, Russia, France, Norway]
    (10) [Canada, America, Russia, France]
    (11) CANADA AMERICA RUSSIA FRANCE 
    (12) is contains Russia ? true
    (13) get(0) : Canada
    (14) lastIndexOf : 2
     * */

ArrayList与LinkedList效率比较：

1、get(index : int) : ArrayList （O(1)），LinkedList （O(n)）

2、addFirst(e : E) ： ArrayList （O(n)），LinkedList （O(1)）

3、removeFirst () ：ArrayList （O(n)） ，LinkedList （O(1)）

其他方法效率都一样

MyArrayList 的开销比MyLinkedList 小，但是，如果要需要在线性表的开始位置插入和删除元素，那么MyLinkedList的效率会高一些。