선형 표

하하,다음은 데이터 구조 와 알고리즘 을 배우 기 시 작 했 습 니 다.학습 과정 에서 의 정리 와 코드 가 데이터 구조 와 알고리즘 을 잘 이해 하 는 데 도움 이 되 기 를 바 랍 니 다.
우선,우 리 는 먼저 가장 간단 한 순서 표를 배운다.
첫 번 째 단 계 는 순서 표 의 기본 정의 와 조작 을 제시 합 니 다.
package net.itaem.list;

/**
 *       ,          
 * 
 * 
 *       :           {a1,a2,a3...an},       :DataType。
 *         ,      ;         ,      ;              
 * 
 * @author    qq:846705189
 * */
public interface List<T> {
	
	/**
	 *               
	 * @param index         
	 * @param element         
	 * */
    public void add(int index, T element);
    
    /**
     *            ,            
     * @param index           
     * @return           
     * */
    public T remove(int index);
    
    /**
     *          
     * @return          
     * */
    public int size();
    
    /**
     *       
     * */
    public void clear();
    
    
}

제2 부 실현 순서 표 의 인터페이스
package net.itaem.list.impl;

import net.itaem.list.List;

/**
 *          List,   java.util.ArrayList
 *        List,          
 * 
 * @author luohong
 * */
public class ArrayList<T> implements List<T> {

	//      
	private int size;  
	//        
	private int length;
	//      ,      ,             ,    Object,           
	Object[] elements;

	/**
	 *        ,       10
	 * */
	public ArrayList(){
		this.length = 10;
	    elements = new Object[10];
	}
	
	/**
	 *       ,       
	 * */
	public ArrayList(int length){
		if(length < 0) throw new RuntimeException("         0");
		if(length > Integer.MAX_VALUE) throw new RuntimeException("            ");
		this.length = length;
		elements = new Object[length];
	}

	@Override
	public void add(int index, T element) {
		//      
		checkIndex(index);
		
		//          ,           
		if(size == length) return;
		
		//            ,    
		if(index == size)
			elements[size] = element;
		else{
			//   index length    index+1 length+1,     
			for(int i=size-1; i>=index; i--) elements[i+1] = elements[i];
		    elements[index] = element;
		}

		//    ,       1
		size++;

	}
	
	@SuppressWarnings("unchecked")
	@Override
	public T remove(int index) {
		//      
		checkIndex(index);
		//    
		T result = null;
		
		//         ,          
		if(index == size-1) {
			result = (T)elements[index];
		    elements[index] = null;
		}else{
			//         ,   index+1 size-1    index size-2
			result = (T)elements[index];
			for(int i=index+1; i<size; i++) {
				elements[i-1] = elements[i];
			}
			
			//         null,           
			elements[size-1] = null;
		}
		
		//    ,     -1
		size--;
		
		return result;
	}

	@Override
	public int size() {
		return size;
	}
	
	public int length(){
		return length;
	}

	@Override
	public void clear() {	
		//            null
		for(int i=0; i<length; i++){
			if(elements[i] != null) elements[i] = null;
		}
		
		//        
		size = 0;
	}

	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for(Object element: elements){
			sb.append(element + ", ");
		}
		//     “,”
		String elementStr = sb.substring(0, sb.length()-2);
		
		return "the ArrayList length is " + length + " and the elements of size is " + size + "; elements is " + elementStr; 
	}

	//              ,              
	private void checkIndex(int index) {
		if(index < 0 || index >= length) throw new RuntimeException("    " + index + "     ,   ");
	}

	public static void main(String[] args){
		//   
		List<Integer> testList = new ArrayList<Integer>(10);
		
		for(int i=0; i<10; i++){
			testList.add(i, i);
		}
		
		System.out.println("before remove
" + testList); System.out.println("remove element is " + testList.remove(8)); System.out.println("after remove
" + testList); System.out.println("add List in index 5 with value 555"); testList.add(5, 555); System.out.println("after add
" + testList); System.out.println("before clear list size " + testList.size()); testList.clear(); System.out.println("after clear list size " + testList.size()); System.out.println(testList); } }

다음은 출력 결과 입 니 다.
before remove
the ArrayList length is 10 and the elements of size is 10; elements is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
remove element is 8
after remove
the ArrayList length is 10 and the elements of size is 9; elements is 0, 1, 2, 3, 4, 5, 6, 7, 9, null
add List in index 5 with value 555
after add
the ArrayList length is 10 and the elements of size is 10; elements is 0, 1, 2, 3, 4, 555, 5, 6, 7, 9
before clear list size 10
after clear list size 0
the ArrayList length is 10 and the elements of size is 0; elements is null, null, null, null, null, null, null, null, null, null

위 에서 사용 하 는 것 은 배열 이 실현 하 는 선형 표 입 니 다.아래 는 체인 식 저장 구 조 를 이용 하여 선형 표를 실현 합 니 다.자바 util.LinkedList 와 유사 합 니 다.여러분 이 관심 이 있 으 면 소스 코드 를 읽 을 수 있 습 니 다.
운행 결과
package net.itaem.list.impl;

import net.itaem.list.List;

/**
 *       。
 *       :           ,          ,              。
 *      ,           。
 * */
public class LinkedList<T> implements List<T>{

	//       ,      ,       ,       
	private class Node<E>{
		//    
		private E data;
		//         
		private Node<E> next;

		/**
		 *         
		 * */
		public Node(E data, Node<E> next){
			this.data = data;
			this.next = next;
		}

		/**
		 *         
		 * */
		public Node(){}

		public Node<E> next(){
			return next;
		}

		public void setNext(Node<E> next){
			this.next = next;
		}

		public E data(){
			return data;
		}
	}


	//       
	private Node<T> head;
	//     
	private int size;
	
	/**
	 *        
	 *        ,        
	 * */
	public LinkedList(){
		head = new Node<T>();	
	}

	
	@Override
	public void add(int index, T element) {
		checkIndex(index);
		if(head == null && index > 0) throw new RuntimeException("    null,   " + index + "    "); 

		size++;

		Node<T> p = head;
		//       
		if(index == size){
			Node<T> newEle = new Node<T>(element, null);

			p.setNext(newEle);

			return;
		}else{

			//   
			for(int i=0; i<index; i++){
				p = p.next();
			}

			//        ,    
			Node<T> newEle = new Node<T>(element, p.next());

			p.setNext(newEle);
		}

	}

	private void checkIndex(int index) {
		if(index < 0) throw new RuntimeException("    " + index + "     ");	
		if(index > size()) throw new RuntimeException("             " + size());
	}


	@Override
	public T remove(int index) {
		checkIndex(index);

		size--;

		T data = null;
		Node<T> p = head;

		if(p != null && p.next() != null){
			for(int i=0; i<index; i++){
				p = p.next();
			}

			data = p.next().data();
			p.setNext(p.next().next());
		}

		return data;
	}

	@Override
	public int size() {

		return size;
	}

	@Override
	public void clear() {
		head = null;
		size = 0;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		Node<T> p = head;
		if(head != null){
			if(p != null && p.next() != null){			
				while(p.next() != null){
					p = p.next();
					sb.append(p.data() + " ");
				}
			}
		}else{
			sb.append("null");
		}
		
		return "the linked list size is " + size + " and the elements is " + sb.toString();
	}

	public static void main(String[] args) {
		LinkedList<Integer> linkedList = new LinkedList<Integer>();

		//    
		for(int i=0; i<10; i++){
			linkedList.add(i, i);
		}
		System.out.println("before add
" + linkedList); linkedList.add(2, 22); System.out.println("affter add
" + linkedList); // remove // :remove , System.out.println("before remove
" + linkedList); System.out.println("remove index 5 and value is " + linkedList.remove(5)); System.out.println("after remove
" + linkedList); // linkedList.clear(); System.out.println("after clear " + linkedList.toString()); } }

총결산
선형 표 는 사실 생활 에서 매우 보편적 이 고 가장 보편적 인 데이터 구조 이다.위의 코드 를 통 해 알 수 있 듯 이 배열 을 통 해 모 의 한 선형 표 는 컴퓨터 의 실현 내부,즉 물리 적 논리 이자 데이터 논리 와 같은 방식 으로 이 루어 진다.물리 적 실현 과정 은 컴퓨터 메모리 가 서로 인접 한 저장 공간 을 개척 한 다음 에 요소 의 선후 순서에 따라 질서 있 게 저장 하 는 것 과 같다.그래서 이런 방식 으로 이 루어 진 순서 표 는 요소 에서 찾 는 것 이 빠 르 고 효율 적 이다.왜냐하면 컴퓨터 는 첫 번 째 요소 와 마지막 요 소 를 찾 든 똑 같이 효율 적 이기 때문이다.
체인 시 계 는 사실 생활 속 에서 도 매우 보편적이다.체인 테이블 의 실현 방식 은 메모리 사용 을 제어 하 는 과정 에서 더욱 우세 하 다.프로그램 은 동적 으로 저장 공간 을 분배 하기 때문이다.삽입 삭제 도 효율 적 이다.왜 더 효율 적 인가요?만약 에 삽입 위치 가 다 르 면 똑 같이 O(n)의 알고리즘 효율 입 니 다.그러나 같은 곳 에 데 이 터 를 삽입 할 때 프로그램 이 이 위 치 를 처음 찾 은 것 은 O(n)이 고 그 다음 에 노드 를 삽입 하 는 것 은 O(1)입 니 다.순서 선형 표 는 삽입 할 때마다 O(n)...
java.util.Array List 와 LinkedList 를 비교 합 니 다.
before add
 the linked list size is 10 and the elements is 0 1 2 3 4 5 6 7 8 9 
affter add
 the linked list size is 11 and the elements is 0 1 22 2 3 4 5 6 7 8 9 
before remove
 the linked list size is 11 and the elements is 0 1 22 2 3 4 5 6 7 8 9 
remove index 5 and value is 4
after remove
 the linked list size is 10 and the elements is 0 1 22 2 3 5 6 7 8 9 
after clear the linked list size is 0 and the elements is null

빨간색 코드 부분 에서 자바 util.Array List 가 get(int index)에 있 을 때 명령 을 실행 하 는 것 만 볼 수 있 습 니 다.삽입,삭제 시 이동 요 소 를 모 를 필요 가 있 습 니 다.
/*
 * %W% %E%
 *
 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */


package java.util;


/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)<p>
 *
 * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.<p>
 *
 * Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.<p>
 *
 * An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 *
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 *
 * <p>The iterators returned by this class's <tt>iterator</tt> and
 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in any way
 * except through the iterator's own <tt>remove</tt> or <tt>add</tt> methods,
 * the iterator will throw a {@link ConcurrentModificationException}.  Thus, in
 * the face of concurrent modification, the iterator fails quickly and cleanly,
 * rather than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.<p>
 *
 * Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i><p>
 *
 * This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @version %I%, %G%
 * @see	    Collection
 * @see	    List
 * @see	    LinkedList
 * @see	    Vector
 * @since   1.2
 */


public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;


    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient Object[] elementData;


    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;


    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param   initialCapacity   the initial capacity of the list
     * @exception IllegalArgumentException if the specified initial capacity
     *            is negative
     */
    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }


    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
	this(10);
    }


    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	size = elementData.length;
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	if (elementData.getClass() != Object[].class)
	    elementData = Arrays.copyOf(elementData, size, Object[].class);
    }


    /**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }


    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }


    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
	return size;
    }


    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
	return size == 0;
    }


    /**
     * Returns <tt>true</tt> if this list contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this list contains
     * at least one element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return <tt>true</tt> if this list contains the specified element
     */
    public boolean contains(Object o) {
	return indexOf(o) >= 0;
    }


    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    public int indexOf(Object o) {
	if (o == null) {
	    for (int i = 0; i < size; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = 0; i < size; i++)
		if (o.equals(elementData[i]))
		    return i;
	}
	return -1;
    }


    /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    public int lastIndexOf(Object o) {
	if (o == null) {
	    for (int i = size-1; i >= 0; i--)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = size-1; i >= 0; i--)
		if (o.equals(elementData[i]))
		    return i;
	}
	return -1;
    }


    /**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone() {
	try {
	    ArrayList<E> v = (ArrayList<E>) super.clone();
	    v.elementData = Arrays.copyOf(elementData, size);
	    v.modCount = 0;
	    return v;
	} catch (CloneNotSupportedException e) {
	    // this shouldn't happen, since we are Cloneable
	    throw new InternalError();
	}
    }


    /**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }


    /**
     * Returns an array containing all of the elements in this list in proper
     * sequence (from first to last element); the runtime type of the returned
     * array is that of the specified array.  If the list fits in the
     * specified array, it is returned therein.  Otherwise, a new array is
     * allocated with the runtime type of the specified array and the size of
     * this list.
     *
     * <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * <tt>null</tt>.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)
     *
     * @param a the array into which the elements of the list are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose.
     * @return an array containing the elements of the list
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this list
     * @throws NullPointerException if the specified array is null
     */
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }


    // Positional Access Operations


    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
 RangeCheck(index);


 return (E) elementData[index];
    }


    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
	RangeCheck(index);


	E oldValue = (E) elementData[index];
	elementData[index] = element;
	return oldValue;
    }


    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }


    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
 if (index > size || index < 0)
     throw new IndexOutOfBoundsException(
 "Index: "+index+", Size: "+size);


 ensureCapacity(size+1);  // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1,
  size - index);
 elementData[index] = element;
 size++;
    }


    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
 RangeCheck(index);


 modCount++;
 E oldValue = (E) elementData[index];


 int numMoved = size - index - 1;
 if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
      numMoved);
 elementData[--size] = null; // Let gc do its work


 return oldValue;
    }


    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }


    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }


    /**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
     */
    public void clear() {
 modCount++;


 // Let gc do its work
 for (int i = 0; i < size; i++)
     elementData[i] = null;


 size = 0;
    }


    /**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }


    /**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(int index, Collection<? extends E> c) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: " + index + ", Size: " + size);


	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount


	int numMoved = size - index;
	if (numMoved > 0)
	    System.arraycopy(elementData, index, elementData, index + numNew,
			     numMoved);


        System.arraycopy(a, 0, elementData, index, numNew);
	size += numNew;
	return numNew != 0;
    }


    /**
     * Removes from this list all of the elements whose index is between
     * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
     * Shifts any succeeding elements to the left (reduces their index).
     * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
     * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
     *
     * @param fromIndex index of first element to be removed
     * @param toIndex index after last element to be removed
     * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
     *              range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
     *              &gt; size() || toIndex &lt; fromIndex)
     */
    protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);


	// Let gc do its work
	int newSize = size - (toIndex-fromIndex);
	while (size != newSize)
	    elementData[--size] = null;
    }


    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }


    /**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
	// Write out element count, and any hidden stuff
	int expectedModCount = modCount;
	s.defaultWriteObject();


        // Write out array length
        s.writeInt(elementData.length);


	// Write out all elements in the proper order.
	for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);


	if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }


    }


    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
	// Read in size, and any hidden stuff
	s.defaultReadObject();


        // Read in array length and allocate array
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];


	// Read in all elements in the proper order.
	for (int i=0; i<size; i++)
            a[i] = s.readObject();
    }
}

빨간색 부분 코드 를 통 해 알 수 있 듯 이 이 클래스 는 내부 클래스 를 정의 하여 노드 를 모 의 한다.java.util.LinkedList 는 요 소 를 찾 을 때 비교적 비효 율 적 이지 만 삽입,삭제 할 때 효율 적 입 니 다.
java.util.Array List 와 java.util.LinkedList 사용 총화
프로그램 이 집합 에 있 는 요 소 를 자주 얻 으 려 면 Array List 를 사용 할 수 있 습 니 다.예 를 들 어 학생 이 로그 인 하려 면 데이터 베이스 에서 모든 데 이 터 를 찾 은 다음 에 하나의 집합 에 넣 은 다음 에 집합 중의 요 소 를 자주 읽 어야 한다.
프로그램 이 자주 집합 에 있 는 요 소 를 삽입 하고 삭제 해 야 한다 면 링크 드 리스트 를 사용 할 수 있다.예 를 들 어 카 트 는 사용자 의 화물 을 집합 에 넣 거나 집합 에서 삭제 해 야 한다.
주의 점
범 형의 기술 을 채 택 했 지만 클래스 안 은 수 조 를 통 해 이 루어 졌 다.하하,범 형 에 대해 서 는 잠시 토론 하지 않 겠 습 니 다.여러분 은 위의 코드 를 먼저 이해 하면 됩 니 다.

좋은 웹페이지 즐겨찾기