数据结构（Java语言）——LinkedList简单实现

下面是一个能够使用的LinkedList泛型类的实现。这里的链表类名为MyLinkedList，避免与类库中反复。

MyLinkedList将作为双链表实现，并且保留到该表两端的引用。这样仅仅要操作发生在已知的位置，就能够保持每一个操作花费常数时间的代价。这个已知的位置能够是端点。也能够是由迭代器指定的一个位置。

设计方面，主要分为三个部分实现：

MyLinkedList类本身，包括到两端的链、表的大小以及一些方法。
Node类，它可能是一个私有的嵌套类。一个节点包括数据以及到前一个节点的链和到下一个节点的链，另一些适当的构造方法。
LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。

包括方法next()，hasNext()，remove()的实现。

import java.util.ConcurrentModificationException;

import java.util.Iterator;

import java.util.NoSuchElementException;

public class MyLinkedList<AnyType> implements Iterable<AnyType> {

	private int theSize;

	private int modCount = 0;

	private Node<AnyType> beginMarker;

	private Node<AnyType> endMarker;

	private static class Node<AnyType> {

		public AnyType data;

		public Node<AnyType> prev;

		public Node<AnyType> next;

		public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {

			data = d;

			prev = p;

			next = n;

		}

	}

	public MyLinkedList() {

		clear();

	}

	public void clear() {

		beginMarker = new Node<AnyType>(null, null, null);

		endMarker = new Node<AnyType>(null, beginMarker, null);

		beginMarker.next = endMarker;

		theSize = 0;

		modCount++;

	}

	public int size() {

		return theSize;

	}

	public boolean isEmpty() {

		return size() == 0;

	}

	public void add(AnyType x) {

		add(size(), x);

	}

	public void add(int idx, AnyType x) {

		addBefore(getNode(idx), x);

	}

	public AnyType get(int idx) {

		return getNode(idx).data;

	}

	public AnyType set(int idx, AnyType newVal) {

		Node<AnyType> p = getNode(idx);

		AnyType oldVal = p.data;

		p.data = newVal;

		return oldVal;

	}

	public AnyType reomve(int idx) {

		return remove(getNode(idx));

	}

	private void addBefore(Node<AnyType> p, AnyType x) {

		Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);

		newNode.prev.next = newNode;

		p.prev = newNode;

		theSize++;

		modCount++;

	}

	private AnyType remove(Node<AnyType> p) {

		p.next.prev = p.prev;

		p.prev.next = p.next;

		theSize--;

		modCount++;

		return p.data;

	}

	private Node<AnyType> getNode(int idx) {

		Node<AnyType> p;

		if (idx < 0 || idx > size()) {

			throw new IndexOutOfBoundsException();

		}

		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;

	}

	public Iterator<AnyType> iterator() {

		return new LinkedListIterator();

	}

	private class LinkedListIterator implements Iterator<AnyType> {

		private Node<AnyType> current = beginMarker.next;

		private int expectedModCount = modCount;

		private boolean okToRemove = false;

		@Override

		public boolean hasNext() {

			return current != endMarker;

		}

		@Override

		public AnyType next() {

			if (modCount != expectedModCount) {

				throw new ConcurrentModificationException();

			}

			if (!hasNext()) {

				throw new NoSuchElementException();

			}

			AnyType nextItem = current.data;

			current = current.next;

			okToRemove = true;

			return nextItem;

		}

		public void remove() {

			if (modCount != expectedModCount) {

				throw new ConcurrentModificationException();

			}

			if (!okToRemove) {

				throw new IllegalStateException();

			}

			MyLinkedList.this.remove(current.prev);

			okToRemove = false;

			expectedModCount++;

		}

	}

}

巴特西

数据结构（Java语言）——LinkedList简单实现

最新文章

热门文章