데이터 구조 (5) - 양 방향 링크

package com.lq.linklist;

public class DoubleLinkedList  
{  
  //    Node  
  private static class Node  
  {  
    Object value;       //   
    Node prev = this;   //   
    Node next = this;   //   

    Node(Object v)  
    {  
      value = v;  
    }  

    public String toString()  
    {  
      return value.toString();  
    }  
  }  
  private Node head = new Node(null); //      
  private int size;                  //     
 
  //          
  public boolean addFirst(Object o)  
  {  
    addAfter(new Node(o), head); //         
    return true;  
  }  
  
  public boolean addLast(Object o)  
  {  
    addBefore(new Node(o), head); //           
    return true;  
  }  

  public boolean add(Object o)  
  {  
    return addLast(o);  
  }  
  
  public boolean add(int index, Object o)  
  {  
    addBefore(new Node(o), getNode(index));  //          
    return true;  
  }  
  
  public boolean remove(int index)  
  {  
    removeNode(getNode(index));  //      
    return true;  
  }  
  
  public boolean removeFirst()  
  {  
    removeNode(head.next);  //        
    return true;  
  }  
  
  public boolean removeLast()  
  {  
    removeNode(head.prev);  //        
    return true;  
  }  
  
  public Object get(int index)  
  {  
    return getNode(index).value; //           
  }  
  
  public int size()  
  {  
    return size; //        
  }  

  public String toString()  
  {  
    StringBuffer s = new StringBuffer("[");  
    Node node = head;  
    for (int i = 0; i < size; i++)  
    {  
      node = node.next;  
      if (i > 0)  
        s.append(", ");  
      s.append(node.value);  
    }  
    s.append("]");  
    return s.toString();  
  }  
  //         

  //      
  private Node getNode(int index)  
  {  
      if (index < 0 || index >= size)  
          throw new IndexOutOfBoundsException();  
        Node node = head.next;  
        for (int i = 0; i < index; i++)  
          node = node.next;  
        return node; 
  }  
  //          
  private void addBefore(Node newNode, Node node)  
  {  
    newNode.prev = node.prev;
    newNode.next = node;
    newNode.next.prev = newNode;
    newNode.prev.next = newNode;
    size++;
  }  
  //          
  private void addAfter(Node newNode, Node node)  
  {  
      newNode.prev = node;
      newNode.next = node.next;
      newNode.next.prev = newNode;
      newNode.prev.next = newNode;
      size++;
  }  
  //      
  private void removeNode(Node node)  
  {  
    node.next.prev = node.prev;
    node.prev.next = node.next;
    node.prev = null;
    node.next = null;
    size--;
  }  
}  

package com.lq.linklist;

public class Test  
{  
public static void main(String[] args)  
{  
  DoubleLinkedList dblink = new DoubleLinkedList();  
  dblink.add("b");  
  dblink.add("c");  
  dblink.add("d");  
  System.out.println(dblink);  

  dblink.addFirst("a");   //       
  System.out.println(dblink);  

  dblink.addLast("f");   //      
  System.out.println(dblink);

  dblink.add(4, "e");   //         
  System.out.println(dblink);  
  
  dblink.remove(2);    //          
  System.out.println(dblink);  

  //            
  System.out.println(dblink.get(1));  

}  
}