Java实现单向链表和双向链表

1、单向链表 单向链表的特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点。

public class Node { Object value; Node next; public Node(String value){ this.value = value; } } public class LinkedListTest { Node first; Node last; public void add(Node node){ if(first == null){ first = node; last = node; }else{ last.next = node; last = node; } } public Node getFirstNode(){ return first; } public Node getLastNode(){ return last; } public int getSize(){ int size = 0; Node node = first; while(node != null){ size ++; node = node.next; } return size; } public static void main(String[] args) { LinkedListTest link = new LinkedListTest(); Node node1 = new Node("node1"); Node node2 = new Node("node2"); Node node3 = new Node("node3"); link.add(node1); link.add(node2); link.add(node3); System.out.println(link.getSize()); System.out.println(link.getFirstNode().value); System.out.println(link.getLastNode().value); } }

2、双向链表 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

public class DoublyNode { Object value; DoublyNode next; DoublyNode pre; public DoublyNode(String value){ this.value = value; } } public class DoublyLinkedListTest { DoublyNode first; DoublyNode last; public void add(DoublyNode node){ if(first == null){ first = node; last = node; }else{ last.next = node; node.pre = last; last = node; last.next = first; first.pre = last; } } public Object remove(Object val) throws Exception{ if(first == null) throw new Exception("empty!"); DoublyNode cur = first; while(cur != null){ if(cur.value.equals(val)){ if(cur == last) last = cur.pre; else cur.next.pre = cur.pre; if(cur == first) first = cur.next; else cur.pre.next = cur.next; return val; } cur = cur.next; } return null; } public int getSize(){ int size = 0; DoublyNode node = first; while(node != null){ size ++; if(node.next == first){ node = null; }else{ node = node.next; } } return size; } public static void main(String[] args) throws Exception { DoublyLinkedListTest link = new DoublyLinkedListTest(); DoublyNode node1 = new DoublyNode("node1"); DoublyNode node2 = new DoublyNode("node2"); DoublyNode node3 = new DoublyNode("node3"); link.add(node1); link.add(node2); link.add(node3); System.out.println(link.remove("node2")); System.out.println(link.getSize()); } }