学步园

/**
 * Introduction to Algorithms, Second Edition 
 * 10.2 LinkedList
 * @author 土豆爸爸
 * 
 */
public class LinkedList {
    /**
     * 链表节点
     */
    public static class Node {
        int key;
        Node prev; //当前节点的前驱节点
        Node next; //当前节点的后继节点
        
        public Node(int key) {
            this.key = key;
        }
    }
    
    private Node head;
    
    /**
     * 查找键值为key的节点
     * @param key 待查找节点的键值
     * @return 键值为key的节点，如果没有找到返回null
     */
    public Node search(int key) {
        Node x = head;
        while(x != null && x.key != key) {
            x = x.next;
        }
        return x;
    }
    
    /**
     * 插入节点x。在链表的最前面插入。
     * @param x 待插入节点
     */
    public void insert(Node x) {
        x.next = head; //使x后继指向原来的head
        if(head != null) {
            head.prev = x; //使x成为原来的head的前驱
        }
        head = x; //使x成为新的head
    }
    
    /**
     * 删除节点x。
     * @param x 待删除节点
     */
    public void delete(Node x) {
        if(x.prev != null) { //如果x不是头节点
            x.prev.next = x.next; //使x的前驱的后继指向x的后继
        } else {
            head = x.next; //否则，使x的后继成为头节点
        }
        
        if(x.next != null) { //如果x不是尾节点
            x.next.prev = x.prev; //使x的后继的前驱指向x的前驱
        }
    }
}

import junit.framework.TestCase;

public class LinkedListTest extends TestCase{
    public void testLinkedList(){
        LinkedList list = new LinkedList();
        LinkedList.Node n1, n2, n3;
        list.insert(n1 = new LinkedList.Node(1));
        list.insert(n2 = new LinkedList.Node(2));
        list.insert(n3 = new LinkedList.Node(3));
        
        assertEquals(n3, list.search(3));
        assertEquals(n2, list.search(2));
        assertEquals(n1, list.search(1));
        assertEquals(n3, n2.prev);
        assertEquals(n1, n2.next);
        
        list.delete(n2);
        assertEquals(n3, n1.prev);
        assertEquals(n1, n3.next);
    }
}