ArrayList
代码语言：javascript
复制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
代码语言：javascript
复制/**
* 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 );
}
}
}
