建站
咨詢
售后
建站咨詢
新聞中心
[[399074]]
一、前言
在前面兩章我們講解了動(dòng)態(tài)數(shù)組、棧和隊(duì)列的講解，這些底層都是依托靜態(tài)數(shù)組，靠 resize解決固定容量問題的，之前雖然用戶看到的是動(dòng)態(tài)數(shù)組，但是依然使用的是靜態(tài)數(shù)組，他是依靠 resize 這個(gè)方法解決 固定容量問題 ，但是我們今天要講解的 鏈表 不一樣，鏈表是我們數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的一個(gè)重點(diǎn)，也有可能是一個(gè)難點(diǎn)，為什么鏈表這么重要呢?因?yàn)樗亲詈?jiǎn)單的也是 真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。
二、為什么鏈表很重要
- 鏈表是一個(gè)真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
- 最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
- 更深入的理解引用(或者指針)
- 更深入的理解遞歸
- 輔助組成其他數(shù)據(jù)結(jié)構(gòu)
更深入的理解引用(或者指針)：和內(nèi)存相關(guān)，雖然在 java 中大家不用手動(dòng)的管理內(nèi)存，但是對(duì) 鏈表 這種數(shù)據(jù)結(jié)構(gòu)，更加深入的理解，可以幫助大家對(duì)引用、指針、甚至計(jì)算機(jī)系統(tǒng)中和內(nèi)存管理相關(guān)的很多話題，有更加深入的認(rèn)識(shí)。
更深入的理解遞歸：鏈表 本來也是有他非常清晰的遞歸結(jié)構(gòu)的，、由于 鏈表 這種數(shù)據(jù)結(jié)構(gòu)是 數(shù)據(jù)結(jié)構(gòu)，我們可以更加 深入理解遞歸，對(duì)于遞歸這種深入理解是不可獲取的。
鏈表 本身也是具有功能性：輔助組成其他數(shù)據(jù)結(jié)構(gòu)(hashMap 、棧和隊(duì)列)
三、什么是鏈表
鏈表 是一種數(shù)據(jù)結(jié)構(gòu)，在內(nèi)存中通過 節(jié)點(diǎn)記錄內(nèi)存地址 而相互鏈接形成一條鏈的儲(chǔ)存方式。相比數(shù)組而言，鏈表在內(nèi)存中不需要連續(xù)的區(qū)域，只需要每一個(gè)節(jié)點(diǎn)都能夠 記錄下一個(gè)節(jié)點(diǎn) 的 內(nèi)存地址 ，通過 引用 進(jìn)行查找，這樣的特點(diǎn)也就造就了 鏈表 增刪操作時(shí)間消耗很小，而查找遍歷時(shí)間消耗很大的特點(diǎn)。
我們?nèi)粘Ｔ?Java 中使用的 LinkedList 即為 雙向鏈表。而在鏈表是由其基本組成單元節(jié)點(diǎn) (Node) 來實(shí)現(xiàn)的。我們?cè)谌粘Ｖ幸姷降逆湵泶蟛糠侄际?單鏈表和雙鏈表
單元節(jié)點(diǎn) (Node)：
- class Node{
- E e;
- Node next;
- }
e 就是鏈表元素
next 指的是當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
對(duì)于 鏈表 來說它就像我們的火車一樣，每一個(gè)節(jié)點(diǎn)其實(shí)就是一節(jié)車廂，我們?cè)谲噹写鎯?chǔ)真正的數(shù)據(jù)，而車廂和車廂之間還要進(jìn)行連接，讓我們數(shù)據(jù)是整合在一起的，用戶可以方便的在所有的數(shù)據(jù)上進(jìn)行查詢或其他操作，那么 數(shù)據(jù)和數(shù)據(jù)連接 就是由這個(gè) next 來完成的
當(dāng)然 鏈表 不能無窮無盡，如果一個(gè)節(jié)點(diǎn)的 next 是 Null 了，就說明這個(gè)節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)了，這就是 鏈表
如下圖所示(單鏈表)：
鏈表的優(yōu)點(diǎn)：真正的動(dòng)態(tài)，不需要處理固定容量的問題鏈表的缺點(diǎn)：?jiǎn)适Я穗S機(jī)訪問的能力
在數(shù)組中：每一個(gè)索引，直接從數(shù)組中拿出索引對(duì)應(yīng)的元素，這是因?yàn)閺牡讓訖C(jī)制上，數(shù)組所開辟的空間，在內(nèi)存里是連續(xù)分布的，所以我們可以直接可以去找這個(gè)數(shù)組的偏移，直接計(jì)算出這個(gè)數(shù)據(jù)所存儲(chǔ)的內(nèi)存地址，可以直接使用。
鏈表：而鏈表是靠 Next 一層一層連接的，需要借助這個(gè) Next 一點(diǎn)一點(diǎn)的去找我們需要取出來的元素。
四、創(chuàng)建我們自己的鏈表
4.1 鏈表基本結(jié)構(gòu)
- /**
- * 底層鏈表的內(nèi)部類
- * @param
- */
- public class LinkedList
{ - //設(shè)計(jì)私有的內(nèi)部類，對(duì)于用戶來說不需要知道鏈表底層實(shí)現(xiàn)，
- // 不需要知道node這個(gè)節(jié)點(diǎn)，對(duì)用戶屏蔽編碼實(shí)現(xiàn)的底層實(shí)現(xiàn)
- private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e,Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- }
內(nèi)部類Node：設(shè)計(jì)私有的內(nèi)部類，對(duì)于用戶來說不需要知道鏈表底層實(shí)現(xiàn)，不需要知道node這個(gè)節(jié)點(diǎn)，對(duì)用戶屏蔽編碼實(shí)現(xiàn)的底層實(shí)現(xiàn)e：元素next：指向Node的一個(gè)引用
4.2 添加元素
之前我們講的是如何在數(shù)組中添加元素，我們?cè)跀?shù)組尾添加元素是非常方便的，因?yàn)閷?duì)于數(shù)組來說是順序排放的，有意思的是對(duì)于鏈表來說，恰恰相反，在鏈表頭添加元素是非常方便的，其實(shí)這樣非常好理解，對(duì)于數(shù)組來說我們有 size 這個(gè)變量，它直接指向了數(shù)組中最后一個(gè)元素下一個(gè)位置，也就是下一個(gè)待添加元素的位置，所以直接添加就非常容易，因?yàn)橛?size 這個(gè)變量，在跟蹤數(shù)組的尾巴，而對(duì)于鏈表來說我們?cè)O(shè)立了鏈表的一個(gè)頭 head ，而沒有變量來跟蹤鏈表的尾巴,所以我們?cè)阪湵眍^添加元素是非常方便的，最關(guān)鍵的就是 node.next = head 和 head = node，如下圖所示：
4.2.1 鏈表頭添加元素
代碼實(shí)現(xiàn)：
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- //方式一
- // Node node = new Node(e);
- // node.next = head;
- // head = node;
- //方式二
- head = new Node(e,head);
- size ++;
- }
4.2.2 鏈表中間添加元素
我們需要在索引為2的地方添加元素 666，我們只需要找到 元素666要 插入之前的節(jié)點(diǎn)(1) ，我們管它叫 prev，然后把 之前節(jié)點(diǎn)的(1) next 指向 666，然后在將 666的這個(gè) 節(jié)點(diǎn)指向之前節(jié)點(diǎn)(1) 的 之后的節(jié)點(diǎn)(2) ，就完成了整個(gè)插入了，其中關(guān)鍵代碼就是 node.next=prev.next和prev.next=node;，其中關(guān)鍵：我們要找到添加節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) 。
代碼實(shí)現(xiàn)：
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- if(index == 0)
- addFirst(e);
- else{
- Node prev = head;
- for (int i = 0; i < index - 1; i++) {//將prev 放入下一個(gè)節(jié)點(diǎn)，直到移動(dòng)到index - 1
- prev = prev.next;
- //方式一
- // Node node = new Node(e);
- // node.next = prev.next;
- // prev.next = node;
- //方式二
- prev.next = new Node(e,prev.next);
- size++;
- }
- }
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
4.2.3 添加操作時(shí)間復(fù)雜度
4.3 為鏈表設(shè)計(jì)虛擬頭結(jié)點(diǎn)
上面我們介紹了鏈表的添加操作，那么我們?cè)谔砑拥臅r(shí)候遇到了一個(gè)問題，就是在鏈表任意一個(gè)地方的時(shí)候，添加一個(gè)元素，在鏈表頭添加一個(gè)元素，和在鏈表其他地方添加元素，邏輯上會(huì)有差別，為什么在鏈表頭添加元素會(huì)比較特殊呢，因?yàn)槲覀冊(cè)阪湵硖砑釉氐倪^程，要找到待添加的 之前的一個(gè)節(jié)點(diǎn)，但是由于對(duì)于鏈表頭沒有之前的一個(gè)節(jié)點(diǎn)，不過我們可以自己創(chuàng)建一個(gè)頭結(jié)點(diǎn)，這個(gè)頭節(jié)點(diǎn)就是 虛擬頭結(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)對(duì)于用戶來說是不存在， 用戶也不會(huì)感知到這個(gè)節(jié)點(diǎn)的存在，我們是屏蔽了這個(gè)節(jié)點(diǎn)的存在，如下圖所示：
代碼實(shí)現(xiàn)：
- private Node dummyHead;
- int size;
- public LinkedList(){
- dummyHead = new Node(null,null);
- size = 0;
- }
- //獲取鏈表中的元素個(gè)數(shù)
- public int getSize(){
- return size;
- }
- //返回鏈表是否為空
- public boolean isEmpty(){
- return size == 0;
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- prev.next = new Node(e,prev.next);
- size ++;
- }
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- add(0,e);
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
4.4 鏈表元素 get、set、是否存在操作
- //在鏈表的index(0-based)位置添加新的元素e
- public E get(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Get failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- return cur.e;
- }
- //獲得鏈表的第一個(gè)元素
- public E getFirst(){
- return get(0);
- }
- //獲取鏈表的最后一個(gè)元素
- public E getLast(){
- return get(size - 1);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void set(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Set failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- cur.e = e;
- }
- //查找鏈表中是否有元素e
- public boolean contains(E e){
- Node cur = dummyHead.next;
- while (cur != null){
- if(cur.e.equals(e))
- return true;
- cur = cur.next;
- }
- return false;
- }
4.5.1 修改和查找操作時(shí)間復(fù)雜度
4.5 刪除鏈表元素
加入我們想要?jiǎng)h除索引為 (2) 位置的元素，我們需要找到 待刪除節(jié)點(diǎn)之前的一個(gè)位置，也就是(1) ，我們用 prev 表示，找到這個(gè)節(jié)點(diǎn)之后，那么 (2) 就是我們需要?jiǎng)h除的索引了 我們叫 delNode，如下圖所示：
代碼實(shí)現(xiàn)：
- //從鏈表中刪除Index(0-based)位置的元素，返回刪除的元素
- public E remove(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Remove failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- Node retNode = prev.next;
- prev.next = retNode.next;
- retNode.next = null;
- size --;
- return retNode.e;
- }
- //從鏈表中刪除第一個(gè)位置的元素
- public E removeFirst(){
- return remove(0);
- }
- //從鏈表中刪除最后一個(gè)位置的元素
- public E removeLast(){
- return remove(size - 1);
- }
4.5.1 刪除操作時(shí)間復(fù)雜度
4.6 完整代碼
- /**
- * 底層鏈表的內(nèi)部類
- * @param
- */
- public class LinkedList
{ - private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e,Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node dummyHead;
- int size;
- public LinkedList(){
- dummyHead = new Node(null,null);
- size = 0;
- }
- //獲取鏈表中的元素個(gè)數(shù)
- public int getSize(){
- return size;
- }
- //返回鏈表是否為空
- public boolean isEmpty(){
- return size == 0;
- }
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- //方式一
- // Node node = new Node(e);
- // node.next = head;
- // head = node;
- //方式二
- add(0,e);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- prev.next = new Node(e,prev.next);
- size ++;
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public E get(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Get failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- return cur.e;
- }
- //獲得鏈表的第一個(gè)元素
- public E getFirst(){
- return get(0);
- }
- //獲取鏈表的最后一個(gè)元素
- public E getLast(){
- return get(size - 1);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void set(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Set failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- cur.e = e;
- }
- //查找鏈表中是否有元素e
- public boolean contains(E e){
- Node cur = dummyHead.next;
- while (cur != null){
- if(cur.e.equals(e))
- return true;
- cur = cur.next;
- }
- return false;
- }
- //從鏈表中刪除Index(0-based)位置的元素，返回刪除的元素
- public E remove(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Remove failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- Node retNode = prev.next;
- prev.next = retNode.next;
- retNode.next = null;
- size --;
- return retNode.e;
- }
- //從鏈表中刪除第一個(gè)位置的元素
- public E removeFirst(){
- return remove(0);
- }
- //從鏈表中刪除最后一個(gè)位置的元素
- public E removeLast(){
- return remove(size - 1);
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- for (Node cur = dummyHead.next;cur != null; cur= cur.next)
- res.append(cur + "->");
- res.append("Null");
- return res.toString();
- }
- }
4.2.7 結(jié)果測(cè)試：
- public static void main(String[] args) {
- LinkedList
linkedList = new LinkedList<>(); - //添加元素 0-4
- for (int i = 0; i < 5 ; i++) {
- linkedList.addFirst(i);
- System.out.println(linkedList);
- }
- //添加第二個(gè)元素添加 666
- linkedList.add(2,666);
- System.out.println(linkedList);
- //刪除第二個(gè)元素 666
- linkedList.remove(2);
- System.out.println(linkedList);
- //刪除第一個(gè)元素
- linkedList.removeFirst();
- System.out.println(linkedList);
- //刪除最后一個(gè)元素
- linkedList.removeLast();
- System.out.println(linkedList);
- }
打印結(jié)果：
- 0->Null
- 1->0->Null
- 2->1->0->Null
- 3->2->1->0->Null
- 4->3->2->1->0->Null
- 4->3->666->2->1->0->Null
- 4->3->2->1->0->Null
- 3->2->1->0->Null
- 3->2->1->Null
四、鏈表時(shí)間復(fù)雜度分析
對(duì)于增加和刪除來說，如果是對(duì)鏈表頭進(jìn)行操作，那么就是 O(1) 級(jí)別的復(fù)雜度，對(duì)于查詢來說，也是一樣
五、鏈表應(yīng)用
5.1 使用棧實(shí)現(xiàn)鏈表
5.1.1 接口類：
- /**
- * @program: Data-Structures
- * @ClassName Stack
- * @description:
- * @author: lyy
- * @create: 2019-11-20 21:51
- * @Version 1.0
- **/
- public interface Stack
{ - int getSize();
- boolean isEmpty();
- void push(E e);
- E pop();
- E peek();
- }
5.1.2 實(shí)現(xiàn)類：
- import com.lyy.datasty.Mystack.Stack;
- //鏈表?xiàng)?shí)現(xiàn)
- public class LinkedListStack
implements Stack { - private LinkedList1
list; - public LinkedListStack(){
- list = new LinkedList1<>();
- }
- @Override
- public int getSize() {
- return list.getSize();
- }
- @Override
- public boolean isEmpty() {
- return list.isEmpty();
- }
- @Override
- public void push(E e) {
- list.addFirst(e);
- }
- @Override
- public E pop() {
- return list.removeFirst();
- }
- @Override
- public E peek() {
- return list.getFirst();
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- res.append("Stack：top ");
- res.append(list);
- return res.toString();
- }
- }
5.1.3 運(yùn)行結(jié)果：
- public static void main(String[] args) {
- LinkedListStack
stack = new LinkedListStack<>(); - for (int i = 0; i < 5; i++) {
- stack.push(i);
- System.out.println(stack);
- }
- stack.pop();
- System.out.println(stack);
- }
5.1.4 結(jié)果打印：
- Stack：top 0->Null
- Stack：top 1->0->Null
- Stack：top 2->1->0->Null
- Stack：top 3->2->1->0->Null
- Stack：top 4->3->2->1->0->Null
- Stack：top 3->2->1->0->Null
5.2 使用鏈表實(shí)現(xiàn)隊(duì)列
5.2.1 接口類
- /**
- * @program: Data-Structures
- * @ClassName Queue
- * @description:
- * @author: lyy
- * @create: 2019-11-21 21:54
- * @Version 1.0
- **/
- public interface Queue
{ - int getSize();
- boolean isEmpty();
- void enqueue(E e);
- E dequeue();
- E getFront();
- }
5.2.2 實(shí)現(xiàn)類
- public class LinkedListQueue
implements Queue { - //設(shè)計(jì)私有的內(nèi)部類，對(duì)于用戶來說不需要知道鏈表底層實(shí)現(xiàn)，
- // 不需要知道node這個(gè)節(jié)點(diǎn)，對(duì)用戶屏蔽編碼實(shí)現(xiàn)的底層實(shí)現(xiàn)
- private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e, Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node head,tail;
- private int size;
- public LinkedListQueue(){
- head = null;
- tail = null;
- size = 0;
- }
- @Override
- public int getSize() {
- return&nb
網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)篇—鏈表
鏈接URL：http://www.dlmjj.cn/article/djhcedo.html
