/**
*
*/
package com.handy.ds;
/**
* @author handy
*2012-03-14
*
*/
public class DoubleLinkedList {
class Node {
Node prev;
Node next;
Object data;
public Node(Object data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public Node(Node prev, Node next) {
this.prev = prev;
this.next = next;
}
public Node() {
}
}
private Node head;
private int size;
/**
* @return the size
*/
public int getSize() {
return size;
}
/**
* @param size
* the size to set
*/
public void setSize(int size) {
this.size = size;
}
private Node getNode(int index) {
checkIndex(index);
Node curr = this.head;
int revIndex = this.size - index;
if (index <= revIndex) {
for (int i = 0; i <= index; i++)
curr = curr.next;
} else {
for (int i = 0; i < revIndex; i++)
curr = curr.prev;
}
return curr;
}
public DoubleLinkedList() {
// 第一个元素存值
head = new Node();
// 头指针不存值，可以这样初始化
head.prev = head.next = head;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
Node curr = this.head.next;
Node last = head.prev;
while ((curr != null || last != null)) {
if (curr.data.equals(o))
return true;
if (last.data.equals(o))
return true;
Node temp = last;
curr = curr.next;
last = last.prev;
if (curr.next == temp)
break; // 指针相碰
}
return false;
// 或者使用以下更简单的方法
// if(indexOf(o)!=-1)
// return true;
// return false;
}
// 移除链表的第一个元素,由于head不保存信息，第一个元素为head.next,故移去head.next
public Object removeFirst() {
if (this.size == 0)
return null;
else {
Node first = head.next;
first.next.prev = head;
head.next = first.next;
this.size--;
return first;
}
}
// 移除最后一个元素
public Object removeLast() {
if (this.size == 0)
return null;
else {
Node last = head.prev;
Node lastSecond = last.prev;
lastSecond.next = head;
head.prev = lastSecond;
this.size--;
return last;
}
}
// 移除第i个元素
public Object remove(int index) throws IndexOutOfBoundsException {
checkIndex(index);
int size = this.size;
Node curr = getNode(index);
Node p = curr.prev;
Node n = curr.next;
p.next = n;
n.prev = p;
this.size--;
return curr;
}
// 移除第一次出现的o元素
public Object removeFist(Object o) {
if (this.size == 0)
return null;
else {
Node curr = this.head.next;
boolean isFind = false;
int size = this.size;
int i = 0;
while (i < size) {
if (curr.data.equals(o)) {
isFind = true;
break;
}
curr = curr.next;
i++;
}
if (isFind) { // 找到就重构链表
Node p = curr.prev;
Node n = curr.next;
p.next = n;
n.prev = p;
this.size--;
return curr;
}
return null;
}
}
// 移除最后一次出现的o元素
public Object removeLastOccurrence(Object o) {
if (this.size == 0)
return null;
else {
Node curr = this.head.next;
Node lastOccurrenceNode = null;
int i = 0;
int size = this.size;
while (i < size) {
if (curr.data.equals(o))
lastOccurrenceNode = curr;