Java入門-コレクション(LinkedList)のインターフェース定義、実装クラス

2014年6月30日

LinkedListはListインターフェースを実装したクラスで、動的配列のようなものです。

要素は重複要素を許し、インスタンス作成時の配列サイズは0です。
1.インターフェース定義
/**
*
* @author arkgame.com
*
*/
public interface MyDeque<E> {

/**
* insert the specified element at the front of this deque if it is possible
* to do so immediately without violating capacity restrictions.
*
* @param e the element to add
*/
void addFirst(E e);

/**
* insert the specified element at the end of this deque if it is possible
* to do so immediately without violating capacity restrictions.
*
* @param e the element to add
*/
void addLast(E e);

/**
* retrieve and remove the first element of this deque.
*
* @return the head of this deque
*/
E removeFirst();

/**
* retrieve and remove the last element of this deque.
*
* @return the tail of this deque
*/
E removeLast();

/**
* insert the specified element into the queue represented by this deque
* (in other words, at the tail of this deque) if it is possible
* to do so immediately without violating capacity restrictions.
*
* @return true upon success
*/
boolean add(E e);

/**
* retrieve and remove the head of this queue represented by this deque
* (in other words, the first element of this deque).
*
* @return the head of the queue represented by this deque
*/
E remove();

/**
* push an element onto the stack represented by this deque
* (in other words, at the head of this deque) if it is possible
* to do so immediately without violating capacity restrictions.
*
* @param e the element to push
*/
void push(E e);

/**
* pop an element from the stack represented by this deque. In other words,
* removes and returns the first element of this deque.
*
* @return the element at the front of this deque
*/
E pop();

/**
* return the number of elements of this dceque.
*
* @return the number of elements of this dceque
*/
public int size();
}
2.カスタムLinkedList実装クラス
/**
*
* @author arkgame.com
*
* @param <E>
*/
public class MyLinkedList<E> implements MyDeque<E>{

private Entry<E> header;
private int size;

public MyLinkedList()
{
header = new Entry<E>(null, null, null);
size = 0;
header.next = header.privious = header;
}

/**
* insert the specified element at the front of this deque if it is possible
* to do so immediately without violating capacity restrictions.
*
* @param e the element to add
*/
public void addFirst(E e) {
addBefore(e, header.next);
}

/**
* insert the specified element at the end of this deque if it is possible
* to do so immediately without violating capacity restrictions.
*
* @param e the element to add
*/
public void addLast(E e) {
addBefore(e, header);
}

/**
* retrieve and remove the first element of this deque.
*
* @return the head of this deque
*/
public E removeFirst() {
return remove(header.next);
}

/**
* retrieve and remove the last element of this deque.
*
* @return the tail of this deque
*/
public E removeLast() {
return remove(header.privious);
}

/**
* pop an element from the stack represented by this deque. In other words,
* removes and returns the first element of this deque.
*
* @return the element at the front of this deque
*/
public E pop() {
return removeFirst();
}

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

/**
* 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.
*
* @return an array containing all of the elements in this list
* in proper sequence
*/
public Object[] toArray()
{
Object[] result = new Object[size];
int i = 0;

for(Entry<E> e=header.next; e!=header; e=e.next)
{
result[i++] = e.element;
}

return result;
}

private static class Entry<E>
{
E element;
Entry<E> privious;
Entry<E> next;

Entry(E element, Entry<E> next, Entry<E> privious)
{
this.element = element;
this.next = next;
this.privious = privious;
}
}

private Entry<E> addBefore(E e, Entry<E> entry)
{
Entry<E> newEntry = new Entry<E>(e, entry, entry.privious);
newEntry.privious.next = newEntry;
newEntry.next.privious = newEntry;

size ++;

return newEntry;
}

private E remove(Entry<E> e)
{
if(e == header)
{
System.out.println(“No such element.");
return null;
}

E result = e.element;
e.privious.next = e.next;
e.next.privious = e.privious;

// let gc do its work
e.privious = null;
e.next = null;
e.element = null;
e = null;

size –;

return result;
}
}

Development

Posted by arkgame