当要创建一个链表的时候，首先要创建一个节点类，在Java里面叫条目（entry表示），这个类是一个嵌套类，里面包含三个要素，element， next， previous。
public class Link<E> {
private static class Entry<E> { private E element; private Entry<E> next; private Entry<E> previous; public Entry(E e, Entry<E> next , Entry<E> previous) { this.element = e; this.next = next; this.previous = previous; } }}创建一个头结点和初始头结点，另外增加一个size用来统计节点数
public class Link<E> {
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0; /** * Constructs an empty list. */ public Link() { header.next = header.previous = header; } private static class Entry<E> { private E element; private Entry<E> next; private Entry<E> previous; public Entry(E e, Entry<E> next , Entry<E> previous) { this.element = e; this.next = next; this.previous = previous; } }}添加和获取、删除节点
package com.hyd.link;
import java.util.NoSuchElementException;
public class Link<E> {
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0; /** * Constructs an empty list. */ public Link() { header.next = header.previous = header; } public int size() { return this.size; } public boolean add(E e) { addBefore(e, header); return true; } public E get(int index) { return entry(index).element; } public E remove(int index) { return remove(entry(index)); } private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size ++; return newEntry; } /** * Returns the indexed entry. */ private Entry<E> entry(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException();E result = e.element;
e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; return result; } private static class Entry<E> { private E element; private Entry<E> next; private Entry<E> previous; public Entry(E e, Entry<E> next , Entry<E> previous) { this.element = e; this.next = next; this.previous = previous; } }}