[数据结构]双向链表实现LinkedList

链表节点的类型定义

private static class Node<AnyType> {
  public AnyType data;
  public Node<AnyType> prev;
  public Node<AnyType> next;

  public Node(AnyType data, Node<AnyType> prev, Node<AnyType> next) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
}

链表的基本成员

private int mListSize;<span style="white-space:pre"></span>\\ 链表长度
private Node<AnyType> mBeginMarker;<span style="white-space:pre"></span>\\ 链表头结点
private Node<AnyType> mEndMarker;<span style="white-space:pre"></span>\\ 链表尾节点

链表初始化

public void clean() {
  mBeginMarker = new Node<AnyType>(null, null, null);
  mEndMarker = new Node<AnyType>(null, mBeginMarker, null);
  mBeginMarker.next = mEndMarker;
  mListSize = 0;
}

链表add操作——在节点p之前加个新节点

private void addBefore(Node<AnyType> p, AnyType value) {
  Node<AnyType> newNode = new Node<AnyType>(value, p.prev, p);
  p.prev.next = newNode;
  p.prev = newNode;
  mListSize++;
}

链表remove操作——移除第index个节点

private AnyType remove(Node<AnyType> item) {
  item.next.prev = item.prev;
  item.prev.next = item.next;
  mListSize--;
  return item.data;
}

链表get操作——获得第index节点

private Node<AnyType> getNode(int index) {
  Node<AnyType> result;
  if (index < 0 || index > size()) {
    throw new IndexOutOfBoundsException();
  }

  if (index < size() / 2) {
    result = mBeginMarker.next;
    for (int i = 0; i < index; i++) {
      result = result.next;
    }
  } else {
    result = mEndMarker;
    for (int i = size(); i > index; i--) {
      result = result.prev;
    }
  }
  return result;
}

完整代码：

public class LinkedListMain {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    // test Integer
    MyLinkedList<Integer> mIntLinkedList = new MyLinkedList<Integer>();
    mIntLinkedList.add(1);  // 1,
    print(mIntLinkedList);
    mIntLinkedList.add(2);  // 1, 2
    print(mIntLinkedList);
    mIntLinkedList.add(3);  // 1, 2, 3
    print(mIntLinkedList);
    mIntLinkedList.add(1, 4); // 1, 4, 2, 3,
    print(mIntLinkedList);
    mIntLinkedList.remove(2); // 1, 4, 3,
    print(mIntLinkedList);
    mIntLinkedList.set(2, 5); // 1, 4, 5,
    print(mIntLinkedList);

    // test String
    MyLinkedList<String> mStringLinkedList = new MyLinkedList<String>();
    mStringLinkedList.add("a"); // a,
    print(mStringLinkedList);
    mStringLinkedList.add("b"); // a, b
    print(mStringLinkedList);
    mStringLinkedList.add("c"); // a, b, c
    print(mStringLinkedList);
    mStringLinkedList.add(1, "d");  // a, d, b, c,
    print(mStringLinkedList);
    mStringLinkedList.remove(2);  // a, d, c,
    print(mStringLinkedList);
    mStringLinkedList.set(2, "e");  // a, d, e,
    print(mStringLinkedList);
  }

  private static void print(MyLinkedList list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i));
    }
    System.out.println(";");
  }

  private static class MyLinkedList<AnyType> {

    private int mListSize;
    private Node<AnyType> mBeginMarker;
    private Node<AnyType> mEndMarker;

    private static class Node<AnyType> {
      public AnyType data;
      public Node<AnyType> prev;
      public Node<AnyType> next;

      public Node(AnyType data, Node<AnyType> prev, Node<AnyType> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
      }
    }

    public MyLinkedList() {
      clean();
    }

    public void clean() {
      mBeginMarker = new Node<AnyType>(null, null, null);
      mEndMarker = new Node<AnyType>(null, mBeginMarker, null);
      mBeginMarker.next = mEndMarker;
      mListSize = 0;
    }

    public int size() {
      return mListSize;
    }

    public void add(AnyType value) {
      add(size(), value);
    }

    public void add(int index, AnyType value) {
      addBefore(getNode(index), value);
    }

    public AnyType remove(int index) {
      return remove(getNode(index));
    }

    public AnyType get(int index) {
      return getNode(index).data;
    }

    public AnyType set(int index, AnyType value) {
      Node<AnyType> old = getNode(index);
      AnyType oldValue = old.data;
      old.data = value;
      return oldValue;
    }

    private void addBefore(Node<AnyType> p, AnyType value) {
      Node<AnyType> newNode = new Node<AnyType>(value, p.prev, p);
      p.prev.next = newNode;
      p.prev = newNode;
      mListSize++;
    }

    private AnyType remove(Node<AnyType> item) {
      item.next.prev = item.prev;
      item.prev.next = item.next;
      mListSize--;
      return item.data;
    }

    private Node<AnyType> getNode(int index) {
      Node<AnyType> result;
      if (index < 0 || index > size()) {
        throw new IndexOutOfBoundsException();
      }

      if (index < size() / 2) {
        result = mBeginMarker.next;
        for (int i = 0; i < index; i++) {
          result = result.next;
        }
      } else {
        result = mEndMarker;
        for (int i = size(); i > index; i--) {
          result = result.prev;
        }
      }
      return result;
    }
  }
}

输出结果：

1;
12;
123;
1423;
143;
145;
a;
ab;
abc;
adbc;
adc;
ade;