1.連結清單(LinkedList)的介紹
總結上圖：
連結清單是一個有序的清單
連結清單不同于數組，連結清單是以結點的形式存儲，在實體空間上不一定連續
連結清單的每個結點的内部包含data(資料)域，next(指針)域，指針域指向下一個結點的位置
連結清單的頭結點不存儲資料，隻是為了指向連結清單的開頭
2.資料聲明
由上圖的分析可知，每個結點應該包括兩部分，一部分為資料，一部分為指針，指向下一個區域，是以我們可以這樣定義:
//定義Node,每個Node對象就是一個結點
class Node{
public String data;
public Node next; //指向下一個結點
//構造器
public Node(String data) {
this.data = data;
}
//toString方法
@Override
public String toString() {
return "Node{" +
"data='" + data + '\'' +
'}';
}
}
在這裡我們通過一個類來表示一個結點，在類中聲明資料及下一個結點next。
3.對連結清單操作的分析
那麼如何對連結清單進行操作呢？
3.1單連結清單初始化
單連結清單的初始化需要對建立一個頭結點
//先初始化一個頭結點，頭結點不能動，頭結點不能變化，友善找到連結清單的頭
private Node head = new Node("這是頭結點");
3.2周遊操作
首先我們應該了解如何周遊整個連結清單，與數組的周遊不同，因為連結清單沒有下标，我們可以拿到的節點隻有頭結點，是以每次進行周遊的時候應該從頭結點開始向後周遊，但因為頭結點的特殊性(不能改變，如果改變，就找不到其他的結點)，我們需要一個輔助的變量temp來進行周遊操作。
Node temp = head;
//周遊連結清單，找到最後
while (temp.next != null){ //如果temp還有下一個結點繼續循環
temp = temp.next; //如果找到了，将結點後移
}
通過循環的操作，不斷對temp指派賦給temp.next，使temp不斷後移，直到an，此時temp.next為空，是以這樣就周遊到了連結清單的尾部。
那麼了解了連結清單的周遊操作我們就可以開始寫連結清單的增删改插入顯示的操作了
3.3增加操作
如上圖示，我們需要對連結清單進行增加操作時，首先需要拿到目前連結清單的最後一個結點，是以需要對連結清單進行周遊操作，然後将temp.next = newNode.next
思路:
1.首先将頭結點head指派給temp，用作周遊時的輔助結點
2.然後進行周遊，直到temp.next=null
3.然後将temp.next=newNode.next，即可完成添加操作
//添加結點到單向連結清單
public void add(Node Node){
//因為head結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head;
//周遊連結清單，找到最後
while (temp.next != null){ //如果temp還有下一個結點繼續循環
temp = temp.next; //如果找到了，将結點後移
}
//當退出while循環時，temp就指向了連結清單的最後
//temp.next指派就好
temp.next = Node;
}
3.4删除操作
如上圖示，我們需要對結點進行删除的時候，應該讓temp指向需要删除的結點的前一個結點，然後将temp.next=temp.next.next,這樣需要删除的結點就沒有引用指向它，就會被java的垃圾回收機制回收
思路：
1.我們需要先周遊到需要删除的結點，如果周遊時還沒有到足夠的次數，就出現了temp.next=null，說明需要删除的結點不存在。
2.當找到後則temp.next=temp.next.next
3.被删除的無引用指向，會被垃圾回收機制删除
3.5插入操作
結點的插入操作需要将新的結點作為參數傳入，首先需要周遊到需要插入的結點，将temp.next=newNode.next,這樣就可以将temp的後面結點的位置賦給newNode.next,然後将temp.next=newNode,這樣就可以把新節點放到需要插入的結點後面
1.我們需要先周遊到需要插入的結點，如果周遊時還沒有到足夠的次數，就出現了temp.next=null，說明需要删除的結點不存在。(原理同3.6)
2.當周遊到需要插入的結點時，newNode=temp.next,temp.next=newNode
//連結清單插入
//找到插入的前一個位置
//temp.dat = node.next
public void insert(Node node,int n){
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
//因為單連結清單，是以我們找的temp是位于添加位置的前一個結點，否則插入不了
if(n <= 0){
System.out.println("資料不合法！");
}
Node temp = head;
boolean flag = false; //标志為是否符合插入條件
for(int i = 0; i < n; i++){
if(temp.next == null){
System.out.println("無法插入結點，插入點不存在");
break;
}
if(i == n - 1 && temp.next != null) {
flag = true;
}
temp = temp.next;
}
if(flag == true){
node.next = temp.next;
temp.next = node;
}
}
3.6修改操作
修改操作非常簡單，周遊至需要修改的結點，将資料進行替換temp.data=Node.data
1.我們需要先周遊到需要修改的結點，如果周遊時還沒有到足夠的次數，就出現了temp.next=null，說明需要删除的結點不存在。(原理同3.6)
2.進行資料替換，temp.data=Node.data
//修改結點的資訊，根據結點位置來修改
public void update(Node newNode,int n){
//判斷是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head;
//找到需要修改的結點，根據傳入的n值
for(int i = 0 ; i < n ; i++){
if(temp.next == null){
System.out.println("該結點不存在");
break;
}
temp = temp.next;
if(i == n-1){
temp.data = newNode.data;
}
}
}
3.6列印操作
列印操作很簡單，周遊每一個結點并把資料列印出來
//顯示連結清單(周遊)
public void list(){
//判斷連結清單是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head.next;
while (temp != null){
System.out.println(temp);
temp = temp.next;
}
}
4.源代碼(含測試用例)
public class SingleLinkedListDemo {
public static void main(String[] args) {
//進行一個測試
//先建立節點
Node node1 = new Node("這是第一個結點");
Node node2 = new Node("這是第二個結點");
Node node3 = new Node("這是第三個結點");
Node node4 = new Node("這是第四個結點");
//建立一個連結清單
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
singleLinkedList.add(node1);
singleLinkedList.add(node2);
singleLinkedList.add(node3);
singleLinkedList.add(node4);
//插入操作
singleLinkedList.insert(new Node("這是插入的結點，應該在第三個結點之後"),3);
//顯示連結清單
singleLinkedList.list();
singleLinkedList.update(new Node("修改了最後一個結點"),5);
singleLinkedList.list();
//連結清單删除
singleLinkedList.delete(4);
singleLinkedList.list();
}
}
//定義SingleLinkedList
class SingleLinkedList{
//先初始化一個頭結點，頭結點不能動，頭結點不能變化，友善找到連結清單的頭
private Node head = new Node("這是頭結點");
//添加結點到單向連結清單
public void add(Node Node){
//因為head結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head;
//周遊連結清單，找到最後
while (temp.next != null){ //如果temp還有下一個結點繼續循環
temp = temp.next; //如果找到了，将結點後移
}
//當退出while循環時，temp就指向了連結清單的最後
//temp.next指派就好
temp.next = Node;
}
//删除結點
//思路
//1.先找到需要删除的結點的前一個結點
//2.temp.next=temp.next.next
//被删除的無引用，會被垃圾回收機制回收
public void delete(int n){
Node temp = head;
for(int i = 0 ; i < n ; i++){
if(temp.next == null){
System.out.println("不存在該結點");
}
if(i == n-1){
temp.next = temp.next.next;
}
temp = temp.next;
}
}
//連結清單插入
//找到插入的前一個位置
//temp.dat = node.next
public void insert(Node node,int n){
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
//因為單連結清單，是以我們找的temp是位于添加位置的前一個結點，否則插入不了
if(n <= 0){
System.out.println("資料不合法！");
}
Node temp = head;
boolean flag = false; //标志為是否符合插入條件
for(int i = 0; i < n; i++){
if(temp.next == null){
System.out.println("無法插入結點，插入點不存在");
break;
}
if(i == n - 1 && temp.next != null) {
flag = true;
}
temp = temp.next;
}
if(flag == true){
node.next = temp.next;
temp.next = node;
}
}
//修改結點的資訊，根據結點位置來修改
public void update(Node newNode,int n){
//判斷是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head;
//找到需要修改的結點，根據傳入的n值
for(int i = 0 ; i < n ; i++){
if(temp.next == null){
System.out.println("該結點不存在");
break;
}
temp = temp.next;
if(i == n-1){
temp.data = newNode.data;
}
}
}
//顯示連結清單(周遊)
public void list(){
//判斷連結清單是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//因為頭結點不能動，是以我們需要一個輔助的周遊temp
Node temp = head.next;
while (temp != null){
System.out.println(temp);
temp = temp.next;
}
}
}
//定義Node,每個Node對象就是一個結點
class Node{
public String data;
public Node next; //指向下一個結點
//構造器
public Node(String data) {
this.data = data;
}
//toString方法
@Override
public String toString() {
return "Node{" +
"data='" + data + '\'' +
'}';
}
}
運作結果
歡迎通路我的個人部落格