(一) 連結串列 – 插入刪除基本操作

NO IMAGE

連結串列:一種用於儲存資料集合的資料結構

連結串列的屬性:1. 相鄰元素之間通過指標連線

                     2.最後一個元素的後繼元素為null

                     3.連結串列的空間可以按需分配(直到系統記憶體耗盡)

                    4.沒有記憶體空間的浪費(但是連結串列當中的指標需要一些額外的記憶體花銷)

連結串列和陣列的區別:

(1)陣列儲存在一塊連續的記憶體空間中,而連結串列的儲存位置不是連續的

(2)當陣列規模很大時,有時沒辦法分配能儲存整個陣列的空間,連結串列則不需要考慮

(3)陣列的大小是靜態的,連結串列可以在常數時間內進行擴充套件

(4)陣列存在陣列下標元素之間又是物理相鄰的,所以陣列的記憶體地址可以通過:資料型別儲存空間的大小*陣列下標 基地址 進行計算,因為運算執行的時間為常數時間所以認為陣列的訪問操作能在常數時間完成,連結串列中查詢特定位置的元素則比較困難,需要遍歷。

(5)陣列基於位置的插入刪除操作比較複雜,較多情況下需要大量移動陣列元素的位置,而連結串列則可以比較簡單的進行插入刪除操作

單向連結串列:

(一)單向連結串列型別宣告

public class ListNode {
private int data;
private ListNode next;
public ListNode(int data){
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
}

(二)計算連結串列元素個數,時間複雜度O(n),空間複雜度O(1)僅用於建立臨時變數

	public int ListLength(ListNode headNode){
int length = 0;
ListNode currentNode = headNode;
while(currentNode!=null){
length  ;
currentNode = currentNode.getNext();
}
return length;
}

(三)單向連結串列的插入

public ListNode InsertInListList(ListNode headNode, ListNode NodeToInsert, int position){
if(headNode == null)
return NodeToInsert;
int size = ListLength(headNode);
if(position>size 1||position<1){
System.out.println("位置錯誤");
                        return null;
                 }
//在連結串列頭部插入
if(position == 1){
NodeToInsert.setNext(headNode);
return NodeToInsert;
}else{
//在連結串列中間或尾部插入
int count = 1;
ListNode currentNode = headNode;
while(count<position-1){
headNode = headNode.getNext();
count  ;
}
ListNode tempNode = headNode.getNext();
NodeToInsert.setNext(tempNode);
headNode.setNext(NodeToInsert);
return currentNode;
}
}

(四)單向連結串列的刪除

	public ListNode DeleteNodeFromLinkedList(ListNode headNode, int position){
int size = ListLength(headNode);
if(position>size||position<1){
System.out.println("位置錯誤");
return null;
}
//刪除連結串列頭部節點
if(position == 1){
return headNode.getNext();
}else{
//刪除連結串列中間和尾部節點
ListNode currentNode = headNode;
int count = 1;
while(count<position-1){
headNode = headNode.getNext();
count  ;
}
ListNode tempNode = headNode.getNext();
headNode.setNext(tempNode.getNext());
return currentNode;
}
}

(五)單連結串列的修改和刪除基於連結串列的遍歷