1.双向链表和单向链表的区别在于双向链表可以从两端遍历,每个节点保存自己的前去节点和后继节点。
2.实现双向链表
package signle; /** * @Author lizhilong * @create 2019/11/8 17:51 * @desc */ public class DoubleDirectionLinkedList { private int size; private Node head; private Node tail; public DoubleDirectionLinkedList() { this.size = 0; this.head = null; this.tail = null; } /** * 往头元素前添加 * * @param data * @return */ public Object addBeforeHead(Object data) { Node newNode = new Node(data); if (size == 0) { newNode.pre = null; newNode.next = null; head = newNode; tail = newNode; } else { newNode.next = head; head.pre = newNode; head = newNode; } size++; return data; } /** * 往尾元素后添加 * * @param data * @return */ public Object addAfterTail(Object data) { Node newNode = new Node(data); if (size == 0) { newNode.pre = null; newNode.next = null; head = newNode; tail = newNode; } else { tail.next = newNode; newNode.pre = tail; tail = newNode; } size++; return data; } /** * 从头元素删除 * * @return */ public Object removeFromHead() { Object data = head.data; head = head.next; size--; return data; } /** * 从尾元素删除 * * @return */ public Object removeFromTail() { Object data = tail.data; tail.pre.next = null; size--; return data; } /** * 删除指定元素 * * @param object * @return */ public boolean remove(Object object) { if (size == 0) { return false; } Node node = head; while (node.data != object) { node = node.next; } node.next.pre = node.pre; node.pre.next = node.next; return true; } /** * 查找指定元素 * * @param data * @return */ public boolean find(Object data) { if (size == 0) { return false; } Node h = head; int index = 0; while (h.data != data) { index++; if(index == size){ break; } h = h.next; } if (index < size) { return true; }else{ return false; } } public void displayFromHead() { Node current = head; StringBuilder builder = new StringBuilder(); builder.append("头---->尾:["); while (current.next != null) { builder.append(current.data.toString() + "->"); current = current.next; } builder.append(current.data.toString()); builder.append("]"); System.out.println(builder.toString()); } public void displayFromTail() { Node current = tail; StringBuilder builder = new StringBuilder(); builder.append("尾---->头:["); while (current.pre != null) { builder.append(current.data.toString() + "->"); current = current.pre; } builder.append(current.data.toString()); builder.append("]"); System.out.println(builder.toString()); } public class Node { private Object data; private Node pre; private Node next; public Node(Object data) { this.data = data; this.pre = null; this.next = null; } } }