目錄
- 1.鏈表
- 2.無頭單向非回圈鏈表
- 3.創建鏈表
- 4.遍歷鏈表
- 5.功能串列
- 5.1查找是否包含關鍵字key是否在單鏈表當中
- 5.2得到單鏈表的長度
- 5.3頭插法
- 5.4尾插法
- 5.5任意位置插入,第一個資料節點為0號下標
- 5.6洗掉第一次出現關鍵字為key的節點
- 5.7洗掉所有值為key的節點
- 5.8清空鏈表
1.鏈表
鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的 ，
鏈表種類：
2.無頭單向非回圈鏈表
結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈
希桶、圖的鄰接表等等，
**注意：**這種鏈表結構的頭不確定，一直在變
例如如果在開始插入節點，那么head會變
下面主要講無頭單向非回圈鏈表
3.創建鏈表
首先用窮舉法創建，只是暫時用，太low了
鏈表是一個一個節點，ListNode代表一個節點
//ListNode代表一個節點
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
5個節點，窮舉法創建：
public ListNode head;//鏈表的頭參考
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
4.遍歷鏈表
用head=head.next的方式進行遍歷，只要當head!=null就行，
注意條件是head!=null
不是this.head.next != null，如果是this.head.next != null最后一個節點不會列印，
但是會出現問題，head變了，所以創建變數cur=this.head,讓cur移動
public void display() {
//this.head.next != null
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
}
}
5.功能串列
5.1查找是否包含關鍵字key是否在單鏈表當中
首先定義ListNode cur = this.head;當cur != null，判斷值是否相等，找到回傳true，否則回傳false：
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
boolean flg = myLinkedList.contains(34);//12,56
System.out.println(flg);
}
}
5.2得到單鏈表的長度
//得到單鏈表的長度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
boolean flg = myLinkedList.contains(12);
System.out.println(flg);
System.out.println(myLinkedList.size());
}
}
5.3頭插法
首先創建node參考：
ListNode node = new ListNode(data);
例如在鏈表頭插入1：
上面兩種方法誰對誰錯呢？
第一種錯了，因為你將它的next改成自己了，后面就連不上了，
注意：系結位置的時候，一定要先系結后面
一個節點都沒有，也可以直接插入
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
boolean flg = myLinkedList.contains(12);
System.out.println(flg);
System.out.println(myLinkedList.size());
myLinkedList.addFirst(45);
myLinkedList.display();
}
}
5.4尾插法
首先要尋找尾巴節點：
尾插法必須判空，因為為空的話，cur為空，cur.next就會報空指標例外
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
myLinkedList.addLast(34);
myLinkedList.addLast(76);
myLinkedList.addLast(100);
myLinkedList.addLast(340);
myLinkedList.display();
}
}
5.5任意位置插入,第一個資料節點為0號下標
如果index=0,就是頭插法,index=size(),就是尾插
/**
* @param index
* @Description:找到index-1位置節點的地址
* @return: ListNode
*/
public ListNode findIndex(int index) {
ListNode cur = this.head;
while ((index - 1) != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法！");
return;
}
if (index == 0) {
addFirst(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
5.6洗掉第一次出現關鍵字為key的節點
首先判斷鏈表是否為空，然后判斷頭結點是否是要找的值，如果不是，后面的節點首先要找到其前驅節點cur
/**
* @param key
* @Description:找要洗掉節點的前驅
* @return: ListNode
*/
public ListNode searchPerv(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//洗掉第一次出現關鍵字為key的節點
public void remove(int key) {
if (this.head == null) {
System.out.println("單鏈表為空,不能洗掉！");
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPerv(key);
if (cur == null) {
System.out.println("沒有要洗掉的節點！");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
myLinkedList.addLast(34);
myLinkedList.addLast(76);
myLinkedList.addLast(100);
myLinkedList.addLast(340);
myLinkedList.display();
myLinkedList.remove(34);
myLinkedList.display();
}
}
5.7洗掉所有值為key的節點
//洗掉所有值為key的節點
public ListNode removeAllKey(int key) {
if (this.head == null) return null;
ListNode perv = this.head;
ListNode cur = this.head.next;
while (cur.next != null) {
if (cur.val == key) {
perv.next = cur.next;
cur = cur.next;
} else {
perv = cur;
cur = cur.next;
}
}
//最后處理頭
if (this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
測驗：洗掉所有的100
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
myLinkedList.addLast(34);
myLinkedList.addLast(76);
myLinkedList.addLast(100);
myLinkedList.addLast(340);
myLinkedList.addFirst(100);
myLinkedList.display();
myLinkedList.removeAllKey(100);
myLinkedList.display();
}
}
5.8清空鏈表
//清空鏈表
public void clear() {
//粗暴的 this.head==null;
while (this.head != null) {
ListNode curNext = head.next;
this.head.next = null;
this.head = curNext;
}
}
測驗：
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();
myLinkedList.addLast(34);
myLinkedList.addLast(76);
myLinkedList.addLast(100);
myLinkedList.addLast(340);
myLinkedList.addFirst(100);
myLinkedList.display();
myLinkedList.removeAllKey(100);
System.out.println("請空前");
myLinkedList.display();
System.out.println("請空后");
myLinkedList.clear();
myLinkedList.display();
System.out.println("==========");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347123.html
標籤：其他