當前位置:成語大全網 - 新華字典 - 用JAVA語言解決:編寫壹個鏈表類(雙向鏈表),實現插入,刪除,查找操作

用JAVA語言解決:編寫壹個鏈表類(雙向鏈表),實現插入,刪除,查找操作

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.next = node;

newNode.prev = node.prev;

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.prev.next = node.next;

node.next.prev = node.prev;

node.prev = null;

node.next = null;

size--;

}

}

//測試類:

public class Test

{

public static void main(String[] args)

{

DoubleLinkedList dll = new DoubleLinkedList();

//添加

dll.add("張三");

dll.add("李四");

dll.add("王五");

System.out.println(dll);

//添加到最前

dll.addFirst("孫七");

System.out.println(dll);

//添加到最後,同添加

dll.addLast("趙六");

System.out.println(dll);

//添加到指定位置

dll.add(4, "王祖賢");

System.out.println(dll);

//移除最前的

dll.removeFirst();

System.out.println(dll);

//移除最後的

dll.removeLast();

System.out.println(dll);

//移除指定位置上的

dll.remove(2);

System.out.println(dll);

//返回指定位置上的元素

System.out.println(dll.get(1));

}

}