鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的地址双戳。
鏈表可分為單向鏈表和雙向鏈表。
一個單向鏈表包含兩個值: 當前節(jié)點的值和一個指向下一個節(jié)點的鏈接糜芳。
image
一個雙向鏈表有三個整數(shù)值: 數(shù)值飒货、向后的節(jié)點鏈接、向前的節(jié)點鏈接峭竣。
image
Java LinkedList（鏈表） 類似于 ArrayList塘辅，是一種常用的數(shù)據(jù)容器。
與 ArrayList 相比皆撩，LinkedList 的增加和刪除對操作效率更高扣墩，而查找和修改的操作效率較低。
以下情況使用 ArrayList :
頻繁訪問列表中的某一個元素扛吞。
只需要在列表末尾進行添加和刪除元素操作呻惕。
以下情況使用 LinkedList :
你需要通過循環(huán)迭代來訪問列表中的某些元素。
需要頻繁的在列表開頭滥比、中間亚脆、末尾等位置進行添加和刪除元素操作。
更多請查看 LinkedList--api
模擬實現(xiàn)：
1守呜、單鏈表：
//定義節(jié)點
static class Node<T> {
public T value;//數(shù)據(jù)域
public Node next;//指針域
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
}
//打印單鏈表
public static void soutNode(Node node) {
System.out.println("node.value: " + node.value);
if (node.next != null) {
soutNode(node.next);
}
}
//打印
//模擬實現(xiàn)單鏈表
Node node3 = new Node("node_3", null);
Node node2 = new Node("node_2", node3);
Node node1 = new Node("node-1", node2);
Node head = new Node("head", node1);
soutNode(head);
打印結(jié)果：
node.value: head
node.value: node-1
node.value: node_2
node.value: node_3
1.1型酥、插入和刪除節(jié)點
//指定位置插入節(jié)點
Node node2_3 = new Node("newNode2_3",node3);
node2.next = node2_3;
//soutNode(newHead);
//刪除某個指定節(jié)點,比如刪除node2
node1.next = node2_3;
soutNode(newHead);
1.2、單項鏈表的反轉(zhuǎn)
原順序是：head查乒、node-1弥喉、node-2、node-3
算法：
//鏈表反轉(zhuǎn)-->head
System.out.println("開始反轉(zhuǎn)>>>>>>>>>");
Node preNode = head;
Node currentNode = head;
Node tempNode;
while (currentNode != null){
tempNode = currentNode.next;//臨存
currentNode.next = preNode;//指針下移
preNode = currentNode;
currentNode = tempNode;//啟用臨時數(shù)據(jù)
}
head.next = null;//原頭結(jié)點next置空
反轉(zhuǎn)后為：node-3玛迄、node-2由境、node-1、head
