生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--链表实现以及应用
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
數據結構與算法–鏈表實現以及應用
- 鏈表是面試時候使用最頻繁的一種數據結構。鏈表的結構簡單，他由指針將若干個節點鏈接成鏈狀結構。鏈表的創建，插入，刪除，查詢操作都只有幾行代碼可以完成，代碼量比較少，可以在較短的時間內完成，這樣可以在短時間內考察出人員對數據結構的理解。而且鏈表數據結構很靈活，可以用來各種靈活的試題。
- 鏈表是一種動態數據結構，因為在建立鏈表的時候，無需知道鏈表的長度，當插入一個節點時候，只需要為新節點分配內存，然后調整鏈表中對應節點的指針指向就可以完成節點的插入。內存分配不是在創建鏈表的時候一次性完成，而是每添加一個節點分配一個節點的內存，由于沒有和數組一樣的閑置的內存，所以鏈表比之數組的內存利用率更高。
- 我們用如下方式定義鏈表節點：
public class ListNode implements Comparable<ListNode> {private String key
;private Integer value
;private ListNode next
;private ListNode before
;public ListNode() {}public ListNode(String key
, Integer value
){this.key
= key
;this.value
= value
;this.next
= null;this.before
= null;}public ListNode(Integer value
) {this.value
= value
;this.next
= null;this.before
= null;}public String getKey() {return key
;}public void setKey(String key
) {this.key
= key
;}public Integer getValue() {return value
;}public void setValue(Integer value
) {this.value
= value
;}public ListNode getNext() {return next
;}public void setNext(ListNode next
) {this.next
= next
;}public ListNode getBefore() {return before
;}public void setBefore(ListNode before
) {this.before
= before
;}@Overridepublic int compareTo(ListNode o
) {return this.value
- o
.value
;}
}
public class MyLinkedList {public static ListNode addToTail(ListNode head
, String key
, Integer value
) {ListNode newNode
= new ListNode(key
, value
);if (head
== null) {head
= newNode
;}else {ListNode pointNode
= head
;while (pointNode
.getNext() != null){pointNode
= pointNode
.getNext();}pointNode
.setNext(newNode
);}return head
;}public static ListNode addToTail(ListNode head
, ListNode newNode
) {if (head
== null) {head
= newNode
;}else {ListNode pointNode
= head
;while (pointNode
.getNext() != null){pointNode
= pointNode
.getNext();}pointNode
.setNext(newNode
);}return head
;}public static void print(ListNode head
){if(head
== null){System.out
.println("is empty list");}ListNode pointNode
= head
;while (pointNode
!= null){System.out
.print(pointNode
.getValue());System.out
.print(", ");pointNode
= pointNode
.getNext();}}public static ListNode search(ListNode head
, Integer value
){if(head
== null || value
== null){System.out
.println("not in");}ListNode pointNode
= head
;while (pointNode
!= null){if(pointNode
.getValue() == value
){System.out
.println("is in");return pointNode
;}else {pointNode
= pointNode
.getNext();}}System.out
.println("not in");return null;}public static ListNode search(ListNode head
, String key
){if(head
== null || key
== null){System.out
.println("not in");}ListNode pointNode
= head
;while (pointNode
!= null){if(pointNode
.getKey().equals(key
)){System.out
.println("is in");return pointNode
;}else {pointNode
= pointNode
.getNext();}}System.out
.println("not in");return null;}public static ListNode delete(ListNode head
, Integer value
){if(head
== null || value
== null || head
.getNext() == null){return head
;}ListNode delNode
= null;if(head
.getValue() == value
){head
= head
.getNext();delNode
= head
;}else {ListNode pointNode
= head
;while (pointNode
.getNext() != null && pointNode
.getNext().getValue() != value
){pointNode
= pointNode
.getNext();}if(pointNode
.getNext() != null && pointNode
.getNext().getValue() == value
){delNode
= pointNode
.getNext();pointNode
.setNext(pointNode
.getNext().getNext());}}if(delNode
!= null){System.out
.println("delete success val="+ delNode
.getValue());}return head
;}public static void main(String[] args
) {Random random
= new Random(100);ListNode myHead
= new ListNode(random
.nextInt(100));for (int i
= 0; i
< 20; i
++) {addToTail(myHead
, random
.nextInt(100));}print(myHead
);if(search(myHead
, 74)){delete(myHead
, 74);}print(myHead
);System.out
.println();System.out
.println();}
}
- 由于鏈表內存不是一次性分配，所以內存是不連續的，通過指針來關鍵每個節點的內存地址，因此我們也不能像數組一樣通過下標去獲取對應的節點，只能從頭開始遍歷節點找到第 i 個節點，時間復雜度是O(n)。
變種題型
- 簡單的單向鏈表實現的基礎上，我們看一個特別的：從尾到頭打印單向鏈表中每個節點值
分析
- 單向鏈表從尾開始打印，簡單的做法是將鏈表中的指針反轉，但是這樣會改變元數據的結構，但是打印一般是只讀的，這樣顯然不可行
- 順序打印可以直接從頭結點開始讀取就可以，要從尾到頭反轉，也就是說有如下特性：第一個先遍歷，但是他必須最后輸出，此時我們可以借助其他的數據結構，將第一次遍歷看出輸入，也就是第一個輸入的必須最后一個輸出，這是典型的先進后出的順序，棧很顯然符合這種標準，我們有如下實現：
public static void printOver(ListNode head
){MyStack myStack
= new MyStack();if(head
== null){return;}ListNode pointNode
= head
;while (pointNode
!= null){myStack
.push(pointNode
.getValue().toString());pointNode
= pointNode
.getNext();}while (!myStack
.isEmpty()){System.out
.print(myStack
.pop());System.out
.print(", ");}}
- 注意：此處用的myStack用的上一節中自己實現的棧，詳情點擊
- 以上實現用棧可以實現，那么一定可以用遞歸來完成，因為遞歸本質上就是棧的一種結構，那么我們用遞歸每次打印節點的時候都判斷是否有子節點，有則下打印子節點，如下實現。
public static void printOver_2(ListNode head
){if(head
== null){return;}ListNode pointNode
= head
;if(pointNode
.getNext() != null){printOver_2(pointNode
.getNext());}System.out
.print(pointNode
.getValue());System.out
.print(", ");}
- 問題：以上遞歸方式的代名詞看起來更簡單一點，但是有一個問題，當鏈表長度非常長的時候，可能會導致函數棧溢出。而之前用棧的方法雖然需要兩次循環但是代碼的魯棒性還是要更好一點，因此我認為最優解是使用棧的方式。
上一篇：數據結構與算法–利用棧實現隊列
下一篇：數據結構與算法–查找與排序另類用法
總結
以上是生活随笔為你收集整理的数据结构与算法--链表实现以及应用的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
