
平台论坛博客文库

› 论坛 › 程序设计 › Java › 用java实现的单链表

用java实现的单链表 [复制链接]

nintyuui

丰衣足食

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2015-06-17 09:58 |只看该作者 |倒序浏览

用java实现的单链表
SingleLinkedList.java

/**
*
*/
package javay.util;
import java.io.Serializable;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
* @author DBJ
*/
public class SingleLinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Serializable, Cloneable {
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
@Override
public boolean hasNext() {
return nextIndex < size;
}
@Override
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
@Override
public boolean hasPrevious() {
return nextIndex > 0;
}
@Override
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : node(previousIndex());
nextIndex--;
return lastReturned.item;
}
@Override
public int nextIndex() {
return nextIndex;
}
@Override
public int previousIndex() {
return nextIndex - 1;
}
@Override
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
@Override
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
@Override
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
/**
* SingleLinkedList
*/
public SingleLinkedList() {
}
/**
* 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 SingleLinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// TODO:called by foreach, contains, toArray, remove, retainAll,get
// at LinkedList, here is binarySearch
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
/*
* @see java.util.AbstractSequentialList#listIterator(int)
*/
@Override
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
/*
* @see java.util.AbstractCollection#size()
*/
@Override
public int size() {
return size;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
Node<E> prev = null;
Node<E> node = first;
// TODO: linkBefore
while(node.next != null) {
prev = node;
if (node == succ) {
break;
}
node = node.next;
}
final Node<E> newNode = new Node<>(e, succ);
if (prev == null)
first = newNode;
else
prev.next = newNode;
size++;
modCount++;
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
Node<E> prev = null;
Node<E> node = first;
// TODO: unlink called by remove, retainAll
boolean bFound = false;
while(node.next != null) {
if (node == x) {
bFound = true;
break;
}
prev = node;
node = node.next;
}
if (bFound == false) {
if (node == x) {
bFound = true;
}
}
if (bFound == false) {
System.out.println("SingleLinkedList@unlink not found." + x);
}
if (prev == null) {
first = node.next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
}

复制代码

java

文库|博客

返回列表

Chinaunix › 论坛 › 程序设计 › Java › 用java实现的单链表

用java实现的单链表 [复制链接]

浏览过的版块