双向链表

/**

* @title <p>双向链表LinkedList</p>
* @author    Jay Chang
* @version 1.0
* @date     2009.8.9
*/

public class LinkedList {
/** 结点内部类:定义结点存的内容，以及前后链接结点引用，以便实现双向链表 */
class Node {
   private Object obj;

   private Node(Object obj) {
    this.obj = obj;
   }

   private Node next;
   private Node prev;
}

/** 定义一个整数包装类 */
class IntegerPackage {
   private IntegerPackage(int value) {
    this.value = value;
   }

   private int value;
}

/** 链表的头尾结点 */
private Node head, rear;
/** 链表总的结点数 */
private int numOfNodes = 0;

/** 链表的构造函数 */
public LinkedList() {
   head = new Node("Head");
   head.prev = null;
   head.next = null;
   rear = head;

}

/** 在链表尾部添加结点 */
public void add(Object obj) {
   Node newNode = new Node(obj);
   Node p = rear;
   p.next = newNode;
   newNode.prev = p;
   newNode.next = null;
   rear = rear.next;
   this.numOfNodes++;
}

/** 在链表头添加结点 */
public void addFirst(Object obj) {
   Node newNode = new Node(obj);
   newNode.prev = head;
   newNode.next = head.next;
   head.next.prev = newNode;
   head.next = newNode;
}

/** 在结点尾部添加，即add() */
public void addLast(Object obj) {
   add(obj);
}

/** 清除所有节点 */
public void clear() {
   this.head = null;
   this.rear = null;
   this.numOfNodes = 0;
   // 为添加结点做准备
   head = new Node("Head");
   head.prev = null;
   head.next = null;
   rear = head;
}

/** 判断是否存在某一结点值为obj,存在则返回该结点，并在包装类中设定该结点索引值 */
private Node isExist(Object obj, IntegerPackage num) {
   Node iterator = this.head;
   int count = num.value;
   while (iterator != null) {
    if (iterator.obj.equals(obj)) {
     break;
    } else {
     iterator = iterator.next;
     count++;
    }
   }
   num.value = count;
   return iterator;
}

/** 判断该链表的所有结点中是否有包含obj对象的，有的话，返回从头结点开始的第一个结点值 */
public boolean contains(Object obj) {
   if (isExist(obj, new IntegerPackage(-1)) != null) {
    return true;
   } else {
    return false;
   }
}

/** 根据索引值查找相应结点的值,不存在返回null */
public Object get(int index) {
   int count = 0;
   Node p = this.head.next;
   while (p != null) {
    if (count == index)
     break;
    p = p.next;
    count++;
   }
   if (p == null)
    return null;
   return p.obj;
}

/** 得到链表头所指向的结点的值 */
public Object getFirst() {
   if (head.next != null) {
    return head.next.obj;
   } else {
    return null;
   }
}

/** 得到链表尾所指向的结点的值 */
public Object getLast() {
   if (rear != null) {
    return rear.obj;
   } else {
    return null;
   }
}

/** 获得包含某一值的结点的索引 */
public int indexOf(Object obj) {
   IntegerPackage count = new IntegerPackage(-1);
   if (isExist(obj, count) == null) {
    return -1;
   }
   return count.value;
}

/** 根据结点值，删除从头结点开始的第一次遇到的那个相应的结点，成功返回true，否则false */
public boolean remove(Object obj) {
   Node iterator = isExist(obj, new IntegerPackage(-1));
   if (iterator == null) {
    return false;
   }
   iterator.prev.next = iterator.next;
   iterator.next.prev = iterator.prev;
   this.numOfNodes--;
   return true;
}

/** 返回所有结点的值 */
public Object[] toArray() {
   Object[] elementData = new Object[this.numOfNodes];
   Node iterator = this.head.next;
   int count = 0;
   while (iterator != null && count != this.numOfNodes) {
    elementData[count++] = iterator;
    iterator = iterator.next;
   }
   return elementData;
}

/** 用toString()方法描述该链表对象 */
public String toString() {
   String info = "[";
   Node p = head.next;
   while (p != null) {
    info += p.obj + " ,";
    p = p.next;
   }
   info = info.substring(0, info.length() - 1) + "]";
   return info;
}

}

评论

1 楼 叶紫夜子 2012-09-22