目錄
一 構(gòu)建一個單向鏈表
二 特點
三 時間復(fù)雜度
四 相關(guān)算法
1.判斷鏈表是否成環(huán)及成環(huán)位置
2.鏈表反轉(zhuǎn)
五 Java中的LinkedList 類
1.使用
2.LinkedList 方法
一 構(gòu)建一個單向鏈表
// 設(shè)計鏈表結(jié)構(gòu)
class ListNode {
? ?int val;
? ?ListNode next;
? ?ListNode(){}
? ?ListNode(int val) {
? ? ? ?this.val=val;
? }
}
// 初始化
class MyLinkedList {
? ?//size存儲鏈表元素的個數(shù)
? ?int size;
? ?//虛擬頭結(jié)點
? ?ListNode head;
?
? ?//初始化鏈表
? ?public MyLinkedList() {
? ? ? ?size = 0;
? ? ? ?head = new ListNode(0);
? }
?
? ?//獲取第index個節(jié)點的數(shù)值
? ?public int get(int index) {
? ? ? ?if (index < 0 || index >= size) {
? ? ? ? ? ?return -1;
? ? ? }
? ? ? ?ListNode currentNode = head;
? ? ? ?for (int i = 0; i <= index; i++) {
? ? ? ? ? ?currentNode = currentNode.next;
? ? ? }
? ? ? ?return currentNode.val;
? }
?
? ?//在鏈表最前面插入一個節(jié)點
? ?public void addAtHead(int val) {
? ? ? ?addAtIndex(0, val);
? }
?
? ?//在鏈表的最后插入一個節(jié)點
? ?public void addAtTail(int val) {
? ? ? ?addAtIndex(size, val);
? }
?
? ?// 在第 index 個節(jié)點之前插入一個新節(jié)點
? ?public void addAtIndex(int index, int val) {
? ? ? ?if (index > size) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?if (index < 0) {
? ? ? ? ? ?index = 0;
? ? ? }
? ? ? ?size++;
? ? ? ?ListNode pred = head;
? ? ? ?for (int i = 0; i < index; i++) {
? ? ? ? ? ?pred = pred.next;
? ? ? }
? ? ? ?ListNode toAdd = new ListNode(val);
? ? ? ?toAdd.next = pred.next;
? ? ? ?pred.next = toAdd;
? }
?
? ?//刪除第index個節(jié)點
? ?public void deleteAtIndex(int index) {
? ? ? ?if (index < 0 || index >= size) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?size--;
? ? ? ?if (index == 0) {
? ? ? ? ? ?head = head.next;
? ?return;
? ? ? }
? ? ? ?ListNode pred = head;
? ? ? ?for (int i = 0; i < index ; i++) {
? ? ? ? ? ?pred = pred.next;
? ? ? }
? ? ? ?pred.next = pred.next.next;
? }
}二 特點
-
長度無限
-
適合任意位置插入和刪除頻繁的場景
-
物理上可以不連續(xù)
三 時間復(fù)雜度
訪問、插入、刪除的時間復(fù)雜度均為O(n）
在頭部插入元素的時間復(fù)雜度為O(1）
四 相關(guān)算法
1.判斷鏈表是否成環(huán)及成環(huán)位置
public ListNode detectCycle(ListNode head) {
? ? ? ?// 判斷是否成環(huán)：快慢指針相遇
? ? ? ?ListNode slow = head;
? ? ? ?ListNode fast = head;
? ? ? ?while (fast != null && fast.next != null) {
? ? ? ? ? ?slow = slow.next;
? ? ? ? ? ?fast = fast.next.next;
? ? ? ? ? ?if (slow == fast) {// 有環(huán)
? ? ? ? ? ? ? ?ListNode index1 = fast; // 相遇節(jié)點
? ? ? ? ? ? ? ?ListNode index2 = head;
? ? ? ? ? ? ? ?// 兩個指針，從頭結(jié)點和相遇結(jié)點，各走一步，直到相遇，相遇點即為環(huán)入口
? ? ? ? ? ? ? ?while (index1 != index2) {
? ? ? ? ? ? ? ? ? ?index1 = index1.next;
? ? ? ? ? ? ? ? ? ?index2 = index2.next;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?return index1;
? ? ? ? ? }
? ? ? }
? ? ? ?return null;
? }2.鏈表反轉(zhuǎn)
public ListNode reverseList(ListNode head) {
? ? ? ?ListNode cur = new ListNode();
? ? ? ?ListNode pre = new ListNode();
? ? ? ?cur = head;
? ? ? ?pre= null;
? ? ? ?while(cur != null ) {
? ? ? ? ? ?ListNode temp = new ListNode();
? ? ? ? ? ?temp = cur.next;
? ? ? ? ? ?cur.next = pre;
? ? ? ? ? ?pre = cur;
? ? ? ? ? ?cur = temp;
? ? ? }
? ? ? ?return pre;
? }五 Java中的LinkedList 類
LinkedList 繼承了 AbstractSequentialList 類。
LinkedList 實現(xiàn)了 Queue 接口，可作為隊列使用。
LinkedList 實現(xiàn)了 List 接口，可進(jìn)行列表的相關(guān)操作。
LinkedList 實現(xiàn)了 Deque 接口，可作為隊列使用。
LinkedList 實現(xiàn)了 Cloneable 接口，可實現(xiàn)克隆。
LinkedList 實現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。文章來源：http://www.zghlxwxcb.cn/news/detail-834254.html
1.使用
LinkedList<String> sites = new LinkedList<String>(); // 創(chuàng)建鏈表
sites.add("Google"); // 添加元素
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites); // 打印輸出鏈表中的元素
sites.addFirst("Wiki"); // 在鏈表頭部添加元素
sites.addLast("Wiki");// 在鏈表尾部添加元素
sites.removeFirst();// 在鏈表頭部刪除元素
sites.removeLast();// 刪除鏈表尾部元素
System.out.println(sites.getFirst());// 獲取鏈表首個元素
System.out.println(sites.getLast());// 獲取鏈表最后一個元素
sites.get(i)// 獲取任意位置元素2.LinkedList 方法
文章來源地址http://www.zghlxwxcb.cn/news/detail-834254.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】每天五分鐘，快速入門數(shù)據(jù)結(jié)構(gòu)（二）——鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
