??????? write in front????????
?????????大家好，我是xiaoxie.希望你看完之后,有不足之處請多多諒解，讓我們一起共同進步????? . ?? ?xiaoxie?????????—CSDN博客
本文由xiaoxie??????????原創(chuàng) CSDN?如需轉載還請通知????
個人主頁：xiaoxie?????????—CSDN博客
系列專欄：xiaoxie的JAVA系列專欄——CSDN博客●'?'σσ??*
我的目標:"團團等我??( ??_?? ?)"?(?????????? )歡迎各位→點贊?? + 收藏?? + 留言???+關注（互三必回）!
目錄
?編輯一.順序表
1.底層實現
2.構造方法
3.常用方法
4.Arrays的遍歷方法
?編輯5.實戰(zhàn)演示
一.順序表
1.底層實現
首先我們要清楚，數據結構是一門邏輯十分清晰的學科，所以我們需要清楚的認識到每個結構的底層是什么，這樣才能更好的掌握這個結構。
2.構造方法
public class Text {
public static void main(String[] args) {
//無參
List<Integer> list = new ArrayList<>();
//指定順序表初始容量
List<Integer> list1 = new ArrayList<>(20);
list1.add(1);
list1.add(11);
//ArrayList(Collection<? extends E> c) 利用其他 Collection 構建 ArrayList
List<Integer> list2 = new ArrayList<>(list1);
}
}
3.常用方法
ArrayList是一個普通的類，實現了List接口，所以它實現了許多接口內的方法，博主現在為大家列舉出一些常用的方法
List<Integer> list = new ArrayList<>();
//尾插入元素
list.add(1);
list.add(12);
list.add(11);
//指定位置插入參數為 位置 和 元素
list.add(2,3);
//順序表長度
list.size();
//刪除指定位置元素
list.remove(2);
//是否包含某個元素
list.contains(4);
//截取部分 list
list.subList(0,1);
//獲取下標 index 位置元素
list.get(2);
//將下標 index 位置元素設置為 element
list.set(3,9);
//返回第一個 o 所在下標
list.indexOf(8);
//返回最后一個 o 的下標
list.lastIndexOf(8);
4.Arrays的遍歷方法
1.直接輸出
List<Integer> list = new ArrayList<>();
//尾插入元素
list.add(1);
list.add(12);
list.add(11);
System.out.println(list);
2.for循環(huán)和for-each
List<Integer> list = new ArrayList<>();
//尾插入元素
list.add(1);
list.add(12);
list.add(11);
System.out.println("for循環(huán)遍歷");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
System.out.println("for-each循環(huán)遍歷");
for (Integer x:list) {
System.out.print(x+" ");
}
3.使用迭代器
List<Integer> list = new ArrayList<>();
//尾插入元素
list.add(1);
list.add(12);
list.add(11);
System.out.println("迭代器正序輸出");
Iterator<Integer>it = list.iterator();
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("迭代器逆序輸出");
ListIterator <Integer> it1 = list.listIterator(list.size());
while (it1.hasPrevious()) {
System.out.print(it1.previous()+" ");
}
}5.實戰(zhàn)演示
楊輝三角?力扣的118題，難度不大，感興趣的朋友可以去嘗試一下
解答代碼如下
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
由圖可知每一行的第一個為1，最后一個也為一中間部分等于上一行的前一個加上上一行同一列的
一個，并且最后一個也為一。
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
List<Integer> list = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
list.add(1);//第一行
ans.add(list);
for(int i = 1;i < numRows;i++) {
List<Integer> temp = new ArrayList<>();
temp.add(1);//每一行的第一個都為一
List<Integer> row =ans.get(i-1);//上一行
for(int j = 1; j <i;j++) {
int x = row.get(j)+row.get(j-1);//中間部分為上一行的前一個加上上一行同一列的一個
temp.add(x);
}
temp.add(1);//一行的最后一個元素也為1
ans.add(temp);
}
return ans;
}
}以上是博主解答這題的思路和代碼，時間復雜度為O（n^2）如果你有更好的方法或者是不懂的地方都可以私聊博主，大家一起交流進步
二.鏈表
1.底層實現
?
當然鏈表的結構不僅僅是這一種其他還有1. 單向或者雙向??2. 帶頭或者不帶頭??3. 循環(huán)或者非循環(huán)
2.無頭單向非循環(huán)鏈表
無頭單向非循環(huán)鏈表是一種數據結構，其特點是沒有頭節(jié)點、只有一個指向第一個節(jié)點的指針，而且最后一個節(jié)點的指針為空（NULL），形成一個單向鏈表的尾部。這意味著如果需要查找第一個節(jié)點，必須從指向第一個節(jié)點的指針開始遍歷鏈表。此外，非循環(huán)鏈表是一個單向鏈表，從第一個節(jié)點開始一直到最后一個節(jié)點，而最后一個節(jié)點指向空（NULL），這樣就可以避免鏈表中的死循環(huán)問題。
3.無頭雙向非循環(huán)鏈表
無頭雙向非循環(huán)鏈表是一種數據結構，它由多個節(jié)點組成，每個節(jié)點有兩個指針，一個指向前一個節(jié)點，一個指向后一個節(jié)點。和單向鏈表不同的是，雙向鏈表可以向前和向后遍歷，而且插入和刪除節(jié)點的操作比較方便。
無頭表示鏈表沒有頭節(jié)點，也就是第一個節(jié)點就是鏈表的起始節(jié)點。非循環(huán)表示鏈表沒有環(huán)，也就是最后一個節(jié)點的指針指向 NULL。
在無頭雙向非循環(huán)鏈表中，我們可以從任意一個節(jié)點開始遍歷，也可以逆序遍歷整個鏈表。雙向鏈表比單向鏈表多了一個指針，所以它在一些場景下比單向鏈表更加方便，比如需要頻繁地插入和刪除節(jié)點時。但是，它也需要更多的內存空間來存儲指針。
4.順序表和鏈表之間的區(qū)別
? ? 順序表和鏈表是兩種數據結構，它們的主要區(qū)別在于存儲方式和操作效率不同：
-
存儲方式不同：順序表使用一組連續(xù)的存儲單元存儲數據，而鏈表則使用指針將一組零散的存儲單元串聯起來。
-
隨機訪問效率不同：順序表通過下標可以直接訪問任意位置的元素，時間復雜度為O(1)，但插入和刪除操作需要移動數據，時間復雜度為O(n)。而鏈表不能通過下標直接訪問元素，插入和刪除操作只需要修改指針，時間復雜度為O(1)，但是隨機訪問需要遍歷整個鏈表，時間復雜度為O(n)。
-
空間利用率不同：順序表預先分配存儲空間大小固定，當存儲空間不夠時需要重新分配內存，可能浪費內存。而鏈表通過動態(tài)分配內存，只在需要時才分配所需的存儲空間，空間利用率較高。
總之，應根據實際需求選擇合適的數據結構，如果需要頻繁隨機訪問，可以選擇順序表；如果需要頻繁插入和刪除，可以選擇鏈表。
5.鏈表面試題
1.給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回?NULL?鏈接
public class Solution {
// 定義一個方法detectCycle，輸入參數為鏈表頭節(jié)點head，返回值類型為ListNode（鏈表節(jié)點）
public ListNode detectCycle(ListNode head) {
// 如果鏈表為空或只有一個元素，則沒有環(huán)，直接返回null
if(head == null || head.next == null) {
return null;
}
// 初始化兩個指針fast和slow，都指向鏈表頭節(jié)點
ListNode fast = head;
ListNode slow = head;
// 使用快慢指針進行遍歷
while(fast != null && fast.next != null) {
// 慢指針每次前進一步
slow = slow.next;
// 快指針每次前進兩步
fast = fast.next.next;
// 如果快慢指針相遇，則說明存在環(huán)
if(slow == fast) {
break;
}
}
// 如果快指針遍歷到鏈表末尾，說明不存在環(huán)，返回null
if(fast == null || fast.next == null) {
return null;
}
// 重新設置快指針fast到鏈表頭節(jié)點，慢指針slow保持在相遇點
fast = head;
// 當快慢指針再次相遇時，相遇點即為環(huán)的起點
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 返回環(huán)的起點
return fast;
}
}2.鏈表的回文結構鏈接
public class PalindromeList {
// 定義一個方法chkPalindrome，輸入參數為鏈表頭節(jié)點head，返回值類型為布爾值（true表示是回文鏈表，false表示不是）
public boolean chkPalindrome(ListNode head) {
// 如果鏈表為空，則直接返回true（空鏈表是回文鏈表）
if(head == null ) {
return true;
}
// 使用快慢指針找到鏈表的中間結點
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next; // 快指針每次前進一步
slow = slow.next; // 慢指針每次前進一步
}
// 翻轉鏈表后半部分
ListNode cur = slow.next;
while(cur != null) {
ListNode curnext = cur.next;
cur.next = slow;
slow = cur;
cur = curnext;
}
// 判斷翻轉后的鏈表與原鏈表前半部分是否相等
while(head != slow) {
if(head.val != slow.val) { // 如果兩個節(jié)點的值不相等，則說明不是回文鏈表
return false;
}if(head.next != slow) { // 奇數情況下，已經比較完所有節(jié)點，可以提前結束循環(huán)
return true;
}
head = head.next; // 頭節(jié)點向后移動一位
slow = slow.next; // 反轉后的尾節(jié)點向前移動一位
}
// 遍歷結束后沒有發(fā)現不相等的節(jié)點，說明是回文鏈表
return true;
}
}3.將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。鏈接文章來源：http://www.zghlxwxcb.cn/news/detail-752916.html
public class Partition {
// 定義一個方法partition，輸入參數為鏈表頭節(jié)點head和整數x，返回值類型為ListNode（鏈表節(jié)點）
public ListNode partition(ListNode head, int x) {
// 如果鏈表為空，則直接返回null
if(head == null) {
return null;
}
// 初始化兩個指針de和dx，用于記錄小于x的元素鏈表的尾節(jié)點和當前節(jié)點
ListNode de = null;
ListNode dx = null;
// 初始化兩個指針pe和px，用于記錄大于等于x的元素鏈表的尾節(jié)點和當前節(jié)點
ListNode pe = null;
ListNode px = null;
// 初始化一個指針cur，指向鏈表的頭節(jié)點
ListNode cur = head;
// 遍歷鏈表中的每個節(jié)點
while(cur != null) {
// 如果當前節(jié)點的值小于x
if(cur.val < x) {
// 如果小于x的元素鏈表尚未創(chuàng)建，則將當前節(jié)點設置為頭節(jié)點和尾節(jié)點
if(de == null) {
de = cur;
dx = cur;
}else { // 否則將當前節(jié)點添加到小于x的元素鏈表的末尾
dx.next = cur;
dx = dx.next;
}
}else { // 如果當前節(jié)點的值大于等于x
// 如果大于等于x的元素鏈表尚未創(chuàng)建，則將當前節(jié)點設置為頭節(jié)點和尾節(jié)點
if(pe == null) {
pe = cur;
px = cur;
}else { // 否則將當前節(jié)點添加到大于等于x的元素鏈表的末尾
px.next = cur;
px = px.next;
}
}
// 指針cur向后移動一位
cur = cur.next;
}
// 如果不存在小于x的元素，則直接返回大于等于x的元素鏈表
if(dx == null) {
return pe;
}
// 將大于等于x的元素鏈表接到小于x的元素鏈表的末尾
dx.next = pe;
// 如果存在大于等于x的元素，則將其尾節(jié)點的next指針置為null
if(pe != null) {
px.next = null;
}
// 返回小于x的元素鏈表的頭節(jié)點
return de;
}
}三.結語
數據結構一門邏輯十分嚴謹的一門學科，而順序表和鏈表都是十分基礎的結構，也是后續(xù)學習的基礎，所以應該要多花時間去搞清楚它的底層，好了本文到這里就結束了，感謝您的閱讀，祝您一天愉快文章來源地址http://www.zghlxwxcb.cn/news/detail-752916.html
到了這里，關于數據結構奇妙旅程之順序表和鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
