java链表——实现LinkedList集合

此处仅实现LinkedList部分方法
1.首先,新建一个接口List类,有以下方法:

import java.util.ArrayList;
import java.util.Collection;
public interface List<E> {
	// 求长度
	int size();
	// 集合内是否有元素
	boolean isEmpty();
	// 某个元素是否在集合内
	boolean contains(Object o);
	// 把集合内元素转换为数组
	Object[] toArray();
	// 向集合内添加元素
	boolean add(E e);
	// 删除集合内的某个元素
	boolean remove(Object o);
	// 删除某个位置的元素
	E remove(int index);
	// 清空集合内元素
	void clear();
	// 根据下标得到集合内某个元素
	E get(int index);
	// 在某个位置添加元素
	void add(int index, E element);
}
此图方便大家理解(使用学生类测试,学生类有id和name属性),

2.在新建一个LinkedList实现类,如下:

public class LinkList<E> implements List<E> {
	@SuppressWarnings("hiding")
	public class Node<E> {
		E item;
		Node<E> next;
		Node<E> prev;
		public Node(Node<E> prev, E element, Node<E> next) {
			super();
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
	}
	private int size;
	Node<E> first = null;
	Node<E> last = null;
	public LinkList() {
	}
	@Override
	public int size() {
		return this.size;
	}
	@Override
	public boolean isEmpty() {
		return (size == 0);
	}
	@Override
	public boolean contains(Object o) {
		return false;
	}
	public int indexOf(Object o) {
		if (o == null) {
			return -1;
		}
		int index = 0;
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				return index;
			}
			index++;
		}
		return -1;
	}
	@Override
	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for (Node<E> x = first; x != null; x = x.next) {
			result[i + 1] = x.item;
		}
		return result;
	}
	void linkLast(E e) {
		Node<E> oldLast = last;
		Node<E> newNode = new Node<>(oldLast, e, null);
		last = newNode;
		if (oldLast == null) {
			first = newNode;
		} else {
			oldLast.next = newNode;
		}
		size++;
	}
	@Override
	public boolean add(E e) {
		linkLast(e);
		return true;
	}
	public void addLast(E e) {
		linkLast(e);
	}
	private void linkFirst(E e) {
		Node<E> oldFirst = first;
		Node<E> newNode = new Node<>(null, e, oldFirst);
		first = newNode;
		if (oldFirst == null) {// 如果集合内没有元素
			last = newNode;// 当前元素也是最后一个元素
		} else {
			oldFirst.prev = newNode;
		}
		size++;
	}
	public void addFirst(E e) {
		linkFirst(e);
	}
	@Override
	public void add(int index, E e) {
		// 范围验证
		if (index >= 0 && index <= size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
		if (index == size) {
			linkLast(e);
		} else {
			Node<E> oldNode = node(index);
		}
	}
	public Node<E> node(int index) {// 根据位置寻找元素
		Node<E> e = first;
		for (int i = 0; i < index; i++) {
			e = e.next;
		}
		return e;
	}
	@Override
	public boolean remove(Object o) {
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				// 开始删除\
				Node<E> p = x.prev;
				Node<E> n = x.next;
				p.next = n;
				n.prev = p;
				x.prev = null;
				x.next = null;
				size--;
				return true;
			}
		}
		return false;
	}
	@Override
	public E remove(int index) {
		// 范围验证
		if (!(index >= 0 && index <= size)) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
		E e = get(index);
		remove(e);
		return e;
	}
	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}
	@Override
	public E get(int index) {
		Node<E> e = first;
		for (int i = 0; i < index; i++) {
			e=e.next;
		}
		return e.item;
	}
	public E removeFirst() {
		Node<E> oldFirst = first;
		//如果只有一个元素
		if (size == 1) {
			first = null;
			last = null;
		} else {
			first = first.next;
			first.prev = null;
		}
		oldFirst.next = null;
		oldFirst.prev = null;
		size --;
		return oldFirst.item;
	}
	public E removeLast() {
		Node<E> oldLast = last;
		//如果只有一个元素
		if (size == 1) {
			first = null;
			last = null;
		} else {
			last = oldLast.prev;
			last.next = null;
		}
		oldLast.next = null;
		oldLast.prev = null;
		size--;
		return oldLast.item;
	}
	public E getFirst() {
		if (first == null) {
			return null;
		} else {
			return last.item;
		}
	}
}