Java 自定义 ArrayList 与 LinkedList
ArrayList
public class MyArrayList<AnyType> implements Iterable<AnyType> {
/** * Construct an empty ArrayList. */
public MyArrayList() {
doClear();
}
/** * Returns the number of items in this collection. * * @return the number of items in this collection. */
public int size() {
return theSize;
}
/** * Returns true if this collection is empty. * * @return true if this collection is empty. */
public boolean isEmpty() {
return size() == 0;
}
/** * Returns the item at position idx. * * @param idx the index to search in. * @throws ArrayIndexOutOfBoundsException if index is out of range. */
public AnyType get(int idx) {
if (idx < 0 || idx >= size())
throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
return theItems[idx];
}
/** * Changes the item at position idx. * * @param idx the index to change. * @param newVal the new value. * @return the old value. * @throws ArrayIndexOutOfBoundsException if index is out of range. */
public AnyType set(int idx, AnyType newVal) {
if (idx < 0 || idx >= size())
throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
AnyType old = theItems[idx];
theItems[idx] = newVal;
return old;
}
@SuppressWarnings("unchecked")
public void ensureCapacity(int newCapacity) {
if (newCapacity < theSize)//当指定的新容量至少和原大小一样时才可以使用
return;
AnyType[] old = theItems;//存储对原始数组的引用
theItems = (AnyType[]) new Object[newCapacity];//为新数组分配内存
for (int i = 0; i < size(); i++)
theItems[i] = old[i];//将旧内容拷贝到新数组
}
/** * Adds an item to this collection, at the end. * * @param x any object. * @return true. */
public boolean add(AnyType x) {
add(size(), x);
return true;
}
/** * Adds an item to this collection, at the specified index. * * @param x any object. * @return true. */
public void add(int idx, AnyType x) {
if (theItems.length == size())
ensureCapacity(size() * 2 + 1);//如果已经满了就扩充容量,变为原来的二倍
for (int i = theSize; i > idx; i--)
theItems[i] = theItems[i - 1];//每一个元素都往后移
theItems[idx] = x;//将数值插入
theSize++;
}
/** * Removes an item from this collection. * * @param idx the index of the object. * @return the item was removed from the collection. */
public AnyType remove(int idx) {
AnyType removedItem = theItems[idx];
for (int i = idx; i < size() - 1; i++)
theItems[i] = theItems[i + 1];
theSize--;
return removedItem;
}
/** * Change the size of this collection to zero. */
public void clear() {
doClear();
}
private void doClear() {
theSize = 0;
ensureCapacity(DEFAULT_CAPACITY);
}
/** * Obtains an Iterator object used to traverse the collection. * * @return an iterator positioned prior to the first element. */
public java.util.Iterator<AnyType> iterator() {
return new ArrayListIterator();
}
/** * Returns a String representation of this collection. */
public String toString() {
StringBuilder sb = new StringBuilder("[ ");
for (AnyType x : this)
sb.append(x + " ");
sb.append("]");
return new String(sb);
}
/** * This is the implementation of the ArrayListIterator. * It maintains a notion of a current position and of * course the implicit reference to the MyArrayList. */
private class ArrayListIterator implements java.util.Iterator<AnyType> {
private int current = 0;//记录当前的值
private boolean okToRemove = false;
public boolean hasNext() {
return current < size();
}
public AnyType next() {
if (!hasNext())
throw new java.util.NoSuchElementException();
okToRemove = true;
return theItems[current++];//将当前位置向后推进
}
public void remove() {
if (!okToRemove)
throw new IllegalStateException();
MyArrayList.this.remove(--current);
okToRemove = false;
}
}
private static final int DEFAULT_CAPACITY = 10;
private AnyType[] theItems;
private int theSize;
}
class TestArrayList {
public static void main(String[] args) {
MyArrayList<Integer> lst = new MyArrayList<>();
for (int i = 0; i < 10; i++)
lst.add(i);
for (int i = 20; i < 30; i++)
lst.add(0, i);
lst.remove(0);
lst.remove(lst.size() - 1);
System.out.println(lst);
}
}
LinkedList
/** * LinkedList class implements a doubly-linked list. */
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
/** * Construct an empty LinkedList. */
public MyLinkedList( )
{
doClear( );
}
private void clear( )
{
doClear( );
}
/** * Change the size of this collection to zero. */
public void doClear( )
{
beginMarker = new Node<>( null, null, null );
endMarker = new Node<>( null, beginMarker, null );
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
/** * Returns the number of items in this collection. * @return the number of items in this collection. */
public int size( )
{
return theSize;
}
public boolean isEmpty( )
{
return size( ) == 0;
}
/** * Adds an item to this collection, at the end. * @param x any object. * @return true. */
public boolean add( AnyType x )
{
add( size( ), x );
return true;
}
/** * Adds an item to this collection, at specified position. * Items at or after that position are slid one position higher. * @param x any object. * @param idx position to add at. * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive. */
public void add( int idx, AnyType x )
{
addBefore( getNode( idx, 0, size( ) ), x );
}
/** * Adds an item to this collection, at specified position p. * Items at or after that position are slid one position higher. * @param p Node to add before. * @param x any object. * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive. */
private void addBefore( Node<AnyType> p, AnyType x )
{
/** * 新加入一个节点,值为x,前驱节点设为加入位置前面的节点,后继节点设为加入位置的节点 * * 然后是声明: * 将该节点赋值给前驱结点的后继节点 * 将该节点的设为原节点的前驱结点 * * 可以简写为: p.prev.next = p.prev = new Node<>(x, p.prev, p); */
Node<AnyType> newNode = new Node<>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
/** * Returns the item at position idx. * @param idx the index to search in. * @throws IndexOutOfBoundsException if index is out of range. */
public AnyType get( int idx )
{
return getNode( idx ).data;
}
/** * Changes the item at position idx. * @param idx the index to change. * @param newVal the new value. * @return the old value. * @throws IndexOutOfBoundsException if index is out of range. */
public AnyType set( int idx, AnyType newVal )
{
Node<AnyType> p = getNode( idx );
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
/** * Gets the Node at position idx, which must range from 0 to size( ) - 1. * @param idx index to search at. * @return internal node corresponding to idx. * @throws IndexOutOfBoundsException if idx is not between 0 and size( ) - 1, inclusive. */
private Node<AnyType> getNode( int idx )
{
return getNode( idx, 0, size( ) - 1 );
}
/** * Gets the Node at position idx, which must range from lower to upper. * @param idx index to search at. * @param lower lowest valid index. * @param upper highest valid index. * @return internal node corresponding to idx. * @throws IndexOutOfBoundsException if idx is not between lower and upper, inclusive. */
private Node<AnyType> getNode( int idx, int lower, int upper )
{
Node<AnyType> p;
if( idx < lower || idx > upper )
throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );
//如果在链表的左半部分就从左边开始遍历
if( idx < size( ) / 2 )
{
p = beginMarker.next;
for( int i = 0; i < idx; i++ )
p = p.next;
}
//否则就从右边开始遍历
else
{
p = endMarker;
for( int i = size( ); i > idx; i-- )
p = p.prev;
}
return p;
}
/** * Removes an item from this collection. * @param idx the index of the object. * @return the item was removed from the collection. */
public AnyType remove( int idx )
{
return remove( getNode( idx ) );
}
/** * Removes the object contained in Node p. * @param p the Node containing the object. * @return the item was removed from the collection. */
private AnyType remove( Node<AnyType> p )
{
/** * 删除p节点只需要将节点的: * p.next.prev = p.prev; * p.prev.next = p.next; */
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++;
return p.data;
}
/** * Returns a String representation of this collection. */
public String toString( )
{
StringBuilder sb = new StringBuilder( "[ " );
for( AnyType x : this )
sb.append( x + " " );
sb.append( "]" );
return new String( sb );
}
/** * Obtains an Iterator object used to traverse the collection. * @return an iterator positioned prior to the first element. */
public java.util.Iterator<AnyType> iterator( )
{
return new LinkedListIterator( );
}
/** * This is the implementation of the LinkedListIterator. * It maintains a notion of a current position and of * course the implicit reference to the MyLinkedList. */
private class LinkedListIterator implements java.util.Iterator<AnyType>
{
//保留一个当前位置
private Node<AnyType> current = beginMarker.next;
private int expectedModCount = modCount;//检测迭代期间集合被修改的情况
private boolean okToRemove = false;
public boolean hasNext( )
{
return current != endMarker;
}
public AnyType next( )
{
if( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException( );
if( !hasNext( ) )
throw new java.util.NoSuchElementException( );
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove( )
{
if( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException( );
if( !okToRemove )
throw new IllegalStateException( );
MyLinkedList.this.remove( current.prev );
expectedModCount++;
okToRemove = false;
}
}
/** * This is the doubly-linked list node. */
private static class Node<AnyType>
{
public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
{
data = d; prev = p; next = n;
}
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}
private int theSize;
private int modCount = 0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
}
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size( ) - 1 );
System.out.println( lst );
java.util.Iterator<Integer> itr = lst.iterator( );
while( itr.hasNext( ) )
{
itr.next( );
itr.remove( );
System.out.println( lst );
}
}
}
查看9道真题和解析
投递完美世界等公司10个岗位 >
