文章目錄
- 1.鏈表的原理
- 1.1鏈表的示意圖
- 1.2鏈表的表現形式
- 1.3結點的分類
- 2.鏈表的代碼表示
- 2.1鏈表的結點定義
- 2.2鏈表的手工創建
- 2.2.1創建一個[1 3 5 6]的鏈表
- 2.2.2創建一個空鏈表
- 2.3遍歷鏈表
- 2.3.1鏈表不知道長度的情況，列印鏈表的元素
- 2.3.2通過遍歷，列印鏈表的最后一個元素
- 2.3.3列印鏈表的倒數第二個元素
- 2.3.4列印鏈表的第n個結點（n>鏈表的長度)
- 2.3.5計算出鏈表中元素的個數
- 2.3.6找到鏈表中是否包含某個元素
1.鏈表的原理
1.1鏈表的示意圖
元素：真實存于線性表中的內容，是我們一般核心關注的內容，
結點（node）；為了組織鏈表而引入的一個結構，除了保存我們的元素之外，還會保存指向下一個結點的參考，
1.2鏈表的表現形式
public class Node {
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
鏈表：最終的線性表，表示邏輯上的[1 3 2 6]
目前，我們通過鏈表的頭節點，來代替一整條鏈表，
//head是一條鏈表的頭結點；通過head我們可以找到找到所有的結點；所以用頭節點來代替鏈表
Node head=...;
//某鏈表的頭節點是null；表示頭節點不存在，進一步可以表示一條沒有頭節點的鏈表，也就是一條空鏈表，
Node head=null;
1.3結點的分類
當前結點（current/cur)：表示鏈表中某個結點
前驅節點(previous/prev):表示鏈表中的某個結點的前一個結點；頭節點沒有前驅節點，
后繼節點（next）：表示鏈表中的某個結點的后一個結點；尾結點沒有后繼節點，
2.鏈表的代碼表示
2.1鏈表的結點定義
public class Node {
public int val;
public Node next;
public Node(int val){
this.val=val;
this.next=null;
}
@Override
public String toString(){
return "Node{"+val+"}";
}
}
2.2鏈表的手工創建
2.2.1創建一個[1 3 5 6]的鏈表
public class myListNode {
public static Node createList(){
Node a=new Node(1);
Node b=new Node(3);
Node c=new Node(5);
Node d=new Node(6);
a.next=b;
b.next=c;
c.next=d;
d.next=null;
return a;
}
}
2.2.2創建一個空鏈表
Node head=null;
2.3遍歷鏈表
2.3.1鏈表不知道長度的情況，列印鏈表的元素
public static void main(String[] args) {
Node head=createList();
Node cur=head;
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
}
2.3.2通過遍歷，列印鏈表的最后一個元素
public static void main(String[] args) {
Node head=createList();
Node cur=head;
while(cur.next!=null){
cur=cur.next;
}
System.out.println(cur.val);
}
2.3.3列印鏈表的倒數第二個元素
public static void main(String[] args) {
Node head=createList();
Node cur=head;
while(cur.next.next!=null){
cur=cur.next;
}
System.out.println(cur.val);
}
2.3.4列印鏈表的第n個結點（n>鏈表的長度)
public static void main(String[] args) {
Node head=createList();
Scanner scanner=new Scanner(System.in);
System.out.println("請輸入一個小于鏈表長度的整數");
int n=scanner.nextInt();
Node cur=head;
int i=0;
for(;i<n;i++){
cur=cur.next;
}
System.out.println(cur.val);
}
2.3.5計算出鏈表中元素的個數
public static void main(String[] args) {
Node head=createList();
Scanner scanner=new Scanner(System.in);
System.out.println("請輸入一個小于鏈表長度的整數");
int n=scanner.nextInt();
Node cur=head;
int i=0;
for(;i<n;i++){
cur=cur.next;
}
System.out.println(cur.val);
}
2.3.6找到鏈表中是否包含某個元素
public static boolean isElement(Node head,int x){
if(head==null){
return false;
}
for(Node cur=head;cur!=null;cur=cur.next){
if(cur.val==x){
return true;
}
}
return false;
}
public static void main(String[] args) {
Node head=createList();
System.out.println(isElement(head,3));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272201.html
標籤：其他