您好,登錄后才能下訂單哦!
這篇文章主要講解了“java數(shù)據(jù)結(jié)構(gòu)中單向鏈表和雙向鏈表的介紹”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“java數(shù)據(jù)結(jié)構(gòu)中單向鏈表和雙向鏈表的介紹”吧!
單向鏈表
單鏈表圖解
代碼
雙向鏈表
編碼
單向鏈表比順序結(jié)構(gòu)的線性表最大的好處就是不用保證存放的位置,它只需要用指針去指向下一個(gè)元素就能搞定。
圖畫的比較粗糙,簡(jiǎn)單的講解一下:
上面四個(gè)長(zhǎng)方形,每個(gè)長(zhǎng)方形都是一個(gè)節(jié)點(diǎn)。在長(zhǎng)方形中,一種包含兩個(gè)東西,一個(gè)是當(dāng)前節(jié)點(diǎn)的元素,一個(gè)是指向下一節(jié)點(diǎn)的地址。這個(gè)下一個(gè)節(jié)點(diǎn)的地址指向了下一個(gè)節(jié)點(diǎn)中的元素。以此類推。
在最左邊的叫做頭節(jié)點(diǎn),同樣,最后面的叫尾節(jié)點(diǎn)。
所以,我們所有的操作都是根據(jù)節(jié)點(diǎn)來(lái)進(jìn)行操作。
這些代碼都有很詳細(xì)的注釋,我就不做過(guò)多的解釋了,你直接到本地idea運(yùn)行一遍就全部知道了。
package com.zxy.lianbiao; /** * @Author Zxy * @Date 2021/2/3 21:25 * @Version 1.0 */ /** * 基于單向鏈表實(shí)現(xiàn)元素的存取 * * @param <E> */ public class MySinglyLinkedList<E> implements MyList<E> { /** * 定義單向鏈表中的節(jié)點(diǎn)對(duì)象 */ class Node<E> { private E item; // 存儲(chǔ)元素 private Node next; // 存儲(chǔ)下一個(gè)節(jié)點(diǎn)對(duì)象 public Node(E item, Node next) { this.item = item; this.next = next; } } private Node head; // 存放鏈表中的頭節(jié)點(diǎn) private int size; // 記錄元素的個(gè)數(shù) /** * 向鏈表中添加元素 * * @param element */ @Override public void add(E element) { // 創(chuàng)建節(jié)點(diǎn) Node<E> node = new Node<>(element, null); // 找到尾節(jié)點(diǎn) Node tail = getTail(); // 節(jié)點(diǎn)的掛接 if (tail == null) { // 如果沒(méi)有尾節(jié)點(diǎn),那意思就是頭節(jié)點(diǎn)都不存在 // 沒(méi)有頭節(jié)點(diǎn),那么就把創(chuàng)建的節(jié)點(diǎn)給頭節(jié)點(diǎn) this.head = node; } else { tail.next = node; } // 記錄元素的個(gè)數(shù) this.size++; } /** * 找尾節(jié)點(diǎn) */ private Node getTail() { // 判斷頭節(jié)點(diǎn)是否存在 if (this.head == null) { return null; } // 查找尾節(jié)點(diǎn) Node node = this.head; while (true) { if (node.next == null) { break; } node = node.next; // 移動(dòng)指針指向下一個(gè) } return node; } /** * 根據(jù)元素的位置獲取元素 * * @param index * @return */ @Override public E get(int index) { // 校驗(yàn)index的合法性 this.checkIndex(index); // 根據(jù)位置獲取指定節(jié)點(diǎn) Node<E> node = this.getNode(index); // 將該節(jié)點(diǎn)中的元素返回 return node.item; } /** * 對(duì)index進(jìn)行校驗(yàn) */ private void checkIndex(int index) { // 0<=index<size if (!(index >= 0 && index < this.size)) { throw new IndexOutOfBoundsException("Index: " + index + " this.size: " + this.size); } } /** * 根據(jù)位置獲取節(jié)點(diǎn) */ private Node<E> getNode(int index) { Node<E> node = this.head; for (int i = 0; i < index; i++) { node = node.next; } return node; } /** * 獲取元素的個(gè)數(shù) * * @return */ @Override public int size() { return this.size; } /** * 根據(jù)元素位置刪除元素 * * @param index * @return */ @Override public E remove(int index) { // 校驗(yàn)index合法性 this.checkIndex(index); // 根據(jù)位置找到節(jié)點(diǎn)對(duì)象 Node<E> node = getNode(index); // 獲取該節(jié)點(diǎn)對(duì)象中的元素 E item = node.item; // 將該節(jié)點(diǎn)對(duì)象從單向鏈表中移除 // 判斷當(dāng)前刪除的節(jié)點(diǎn)是否為頭節(jié)點(diǎn) if (this.head == node) { this.head = node.next; } else { Node<E> temp = this.head; for (int i = 0; i < index - 1; i++) { temp = temp.next; // 此時(shí)的temp就是要?jiǎng)h除的那個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) } temp.next = node.next; // 將當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn) } // 然后將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向null node.next = null; // 記錄元素個(gè)數(shù) this.size--; // 將該元素返回 return item; } /** * 插入節(jié)點(diǎn)思路:如果當(dāng)前共有三個(gè)節(jié)點(diǎn)分別是1,2,3,在1和2的中間插入4,原本的指向是1->2 現(xiàn)改變成1->4 4->2 先獲取到指定位置的node,再獲取到前一個(gè)位置的node和下一個(gè)位置的node */ public void insert(int index, E element) { // 先根據(jù)要插入的位置拿到這個(gè)位置的節(jié)點(diǎn)對(duì)象 Node<E> item = getNode(index); // 根據(jù)插入的元素新建一個(gè)節(jié)點(diǎn) Node<E> eNode = new Node<>(element, null); // 如果是頭節(jié)點(diǎn),那么就找不到前一個(gè),直接把這個(gè)賦值給head if (index == 0){ // index==0代表是替換掉頭節(jié)點(diǎn) this.head = eNode; eNode.next = item; this.size++; }else { // 根據(jù)當(dāng)前的節(jié)點(diǎn)對(duì)象去找到前一個(gè)節(jié)點(diǎn)對(duì)象和后一個(gè)節(jié)點(diǎn)對(duì)象 Node<E> before = this.head; // 根據(jù)頭節(jié)點(diǎn)去找 for (int i = 0; i < index - 1; i++) { before = before.next; // 此時(shí)的before就是當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) } before.next = eNode; eNode.next = item; this.size++; } } public static void main(String[] args) { MySinglyLinkedList<String> list = new MySinglyLinkedList<>(); System.out.println("添加節(jié)點(diǎn)開始------------------------"); list.add((String) "a"); list.add((String) "b"); list.add((String) "c"); list.add((String) "d"); System.out.println("添加節(jié)點(diǎn)完成-------------------------\n"); System.out.println("插入指定的元素"); list.insert(0,"f"); for (int i = 0; i < list.size; i++) { System.out.println(list.get(i)); } } }
昨天寫完單向鏈表和棧結(jié)構(gòu)之后,看了看程杰大大的書中有介紹雙向鏈表的部分。雖然是c語(yǔ)言寫的,但是我還是用Java給翻譯出來(lái)了。
思路如下:
首先,雙向鏈表和單向鏈表的最大區(qū)別就是,雙向鏈表比單鏈表多了個(gè)指向前一節(jié)點(diǎn)的指針。代碼量其實(shí)并不比單鏈表多很多,只是思路的轉(zhuǎn)變需要克服一下。
其次就是在插入元素的時(shí)候,我們可以在鏈表的頭部插入,也可以在鏈表的尾部插入(因?yàn)橛袃蓚€(gè)指針嘛)
代碼其實(shí)和單鏈表差不多,如果感興趣的話可以去看看我之前寫的單鏈表的文章。雖然文筆很爛,但是代碼貨真價(jià)實(shí)。
package com.zxy.lianbiao; /** * @Author Zxy * @Date 2021/2/4 20:11 * @Version 1.0 */ /** * 基于雙向鏈表實(shí)現(xiàn)元素存取的容器 * * @param <E> */ public class MyDoublyLinkedList<E> implements MyList<E> { /** * 定義雙向鏈表節(jié)點(diǎn)對(duì)象 */ class Node<E> { E item; // 記錄元素 Node<E> prev; // 記錄前一個(gè)節(jié)點(diǎn)對(duì)象 Node<E> next; // 記錄下一個(gè)節(jié)點(diǎn)對(duì)象 public Node(Node<E> prev, E item, Node<E> next) { this.item = item; this.prev = prev; this.next = next; } } private Node head; // 記錄頭節(jié)點(diǎn) private Node tail; // 記錄尾節(jié)點(diǎn) private int size; // 記錄元素個(gè)數(shù) /** * 向雙向鏈表中添加元素的方法 * * @param element */ @Override public void add(E element) { linkLast(element); } /** * 將節(jié)點(diǎn)對(duì)象添加到雙向鏈表的尾部 */ private void linkLast(E element) { Node t = this.tail; // 獲取尾節(jié)點(diǎn) Node<E> node = new Node<>(t, element, null); // 創(chuàng)建節(jié)點(diǎn)對(duì)象 this.tail = node; // 將新節(jié)點(diǎn)定義為尾節(jié)點(diǎn) 因?yàn)樵瓉?lái)的尾節(jié)點(diǎn)被這個(gè)新節(jié)點(diǎn)替代了 if (t == null) { // 說(shuō)明一個(gè)節(jié)點(diǎn)都沒(méi)有,這個(gè)還得是頭節(jié)點(diǎn) this.head = node; } else { t.next = node; } this.size++; } /** * 根據(jù)指定位置獲取元素 * * @param index * @return */ @Override public E get(int index) { this.checkIndex(index); // 根據(jù)位置查找節(jié)點(diǎn)對(duì)象 Node<E> node = this.getNode(index); return node.item; } /** * 對(duì)index的合法性校驗(yàn) */ private void checkIndex(int index) { if (!(index >= 0 && index < this.size)) { throw new IndexOutOfBoundsException(); } } /** * 根據(jù)位置獲取指定節(jié)點(diǎn)對(duì)象 */ private Node getNode(int index) { // 判斷當(dāng)前位置距離頭或者尾哪個(gè)節(jié)點(diǎn)更近 使用二分法 if (index < (this.size >> 1)) { Node node = this.head; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { Node node = this.tail; for (int i = this.size - 1; i > index; i--) { node = node.prev; } return node; } } /** * 返回元素的個(gè)數(shù) * * @return */ @Override public int size() { return this.size; } /** * 刪除元素 * * @param index * @return */ @Override public E remove(int index) { // 對(duì)index進(jìn)行合法性校驗(yàn) this.checkIndex(index); Node node = this.getNode(index); // 根據(jù)位置獲取到節(jié)點(diǎn)對(duì)象 // 獲取節(jié)點(diǎn)對(duì)象的元素 E item = (E) node.item; // 判斷當(dāng)前節(jié)點(diǎn)是否為頭節(jié)點(diǎn) if (node.prev == null) { this.head = node.next; } else { node.prev.next = node.next; } // 判斷當(dāng)前節(jié)點(diǎn)是否為尾節(jié)點(diǎn) if (node.next == null) { // node.prev.next = null; this.tail = node.prev; } else { node.next.prev = node.prev; } // 當(dāng)前節(jié)點(diǎn)斷掉與他后繼節(jié)點(diǎn)的連接 node.next = null; // 當(dāng)前節(jié)點(diǎn)斷掉與直接前驅(qū)節(jié)點(diǎn)的連接 node.prev = null; node.item = null; this.size--; return item; } /** * 在雙向鏈表的頭添加元素 */ public void addFirst(E element) { this.linkFirst(element); } /** * 在鏈表的頭添加元素 * * @param element */ public void linkFirst(E element) { // 獲取頭節(jié)點(diǎn)對(duì)象 Node head = this.head; Node<E> eNode = new Node<>(null, element, head); // 將新節(jié)點(diǎn)定義為頭節(jié)點(diǎn) this.head = eNode; if (head == null) { // 如果為空,說(shuō)明該鏈表中一個(gè)節(jié)點(diǎn)都沒(méi)有 也就是該頭節(jié)點(diǎn)也是尾節(jié)點(diǎn) this.tail = eNode; } else { head.prev = eNode; } this.size++; } /** * 在鏈表的尾部添加元素 * * @param element */ public void addLast(E element) { this.linkLast(element); } public static void main(String[] args) { MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>(); list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); System.out.println(list.remove(2)); System.out.println(list.size); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } }
感謝各位的閱讀,以上就是“java數(shù)據(jù)結(jié)構(gòu)中單向鏈表和雙向鏈表的介紹”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)java數(shù)據(jù)結(jié)構(gòu)中單向鏈表和雙向鏈表的介紹這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。