java數據結構基礎:單,雙向鏈表
更新時間：2021年07月27日 15:37:40 作者：魚小洲
這篇文章主要介紹了Java的數據解構基礎，希望對廣大的程序愛好者有所幫助，同時祝大家有一個好成績,需要的朋友可以參考下，希望能給你帶來幫助
單向鏈表
單向鏈表比順序結構的線性表最大的好處就是不用保證存放的位置，它只需要用指針去指向下一個元素就能搞定。
單鏈表圖解
圖畫的比較粗糙，簡單的講解一下：
上面四個長方形，每個長方形都是一個節(jié)點。在長方形中，一種包含兩個東西，一個是當前節(jié)點的元素，一個是指向下一節(jié)點的地址。這個下一個節(jié)點的地址指向了下一個節(jié)點中的元素。以此類推。
在最左邊的叫做頭節(jié)點，同樣，最后面的叫尾節(jié)點。
所以，我們所有的操作都是根據節(jié)點來進行操作。
代碼
這些代碼都有很詳細的注釋，我就不做過多的解釋了，你直接復制代碼到本地idea運行一遍就全部知道了。
package com.zxy.lianbiao;
/**
* @Author Zxy
* @Date 2021/2/3 21:25
* @Version 1.0
*/
/**
* 基于單向鏈表實現元素的存取
*
* @param <E>
*/
public class MySinglyLinkedList<E> implements MyList<E> {
/**
* 定義單向鏈表中的節(jié)點對象
*/
class Node<E> {
private E item; // 存儲元素
private Node next; // 存儲下一個節(jié)點對象
public Node(E item, Node next) {
this.item = item;
this.next = next;
}
}
private Node head; // 存放鏈表中的頭節(jié)點
private int size; // 記錄元素的個數
/**
* 向鏈表中添加元素
*
* @param element
*/
@Override
public void add(E element) {
// 創(chuàng)建節(jié)點
Node<E> node = new Node<>(element, null);
// 找到尾節(jié)點
Node tail = getTail();
// 節(jié)點的掛接
if (tail == null) { // 如果沒有尾節(jié)點，那意思就是頭節(jié)點都不存在
// 沒有頭節(jié)點，那么就把創(chuàng)建的節(jié)點給頭節(jié)點
this.head = node;
} else {
tail.next = node;
}
// 記錄元素的個數
this.size++;
}
/**
* 找尾節(jié)點
*/
private Node getTail() {
// 判斷頭節(jié)點是否存在
if (this.head == null) {
return null;
}
// 查找尾節(jié)點
Node node = this.head;
while (true) {
if (node.next == null) {
break;
}
node = node.next; // 移動指針指向下一個
}
return node;
}
/**
* 根據元素的位置獲取元素
*
* @param index
* @return
*/
@Override
public E get(int index) {
// 校驗index的合法性
this.checkIndex(index);
// 根據位置獲取指定節(jié)點
Node<E> node = this.getNode(index);
// 將該節(jié)點中的元素返回
return node.item;
}
/**
* 對index進行校驗
*/
private void checkIndex(int index) {
// 0<=index<size
if (!(index >= 0 && index < this.size)) {
throw new IndexOutOfBoundsException("Index: " + index + " this.size: " + this.size);
}
}
/**
* 根據位置獲取節(jié)點
*/
private Node<E> getNode(int index) {
Node<E> node = this.head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 獲取元素的個數
*
* @return
*/
@Override
public int size() {
return this.size;
}
/**
* 根據元素位置刪除元素
*
* @param index
* @return
*/
@Override
public E remove(int index) {
// 校驗index合法性
this.checkIndex(index);
// 根據位置找到節(jié)點對象
Node<E> node = getNode(index);
// 獲取該節(jié)點對象中的元素
E item = node.item;
// 將該節(jié)點對象從單向鏈表中移除
// 判斷當前刪除的節(jié)點是否為頭節(jié)點
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; // 此時的temp就是要刪除的那個節(jié)點的前一個節(jié)點
}
temp.next = node.next; // 將當前節(jié)點的前一個節(jié)點指向當前節(jié)點的后一個節(jié)點
}
// 然后將當前節(jié)點的下一個節(jié)點指向null
node.next = null;
// 記錄元素個數
this.size--;
// 將該元素返回
return item;
}
/**
* 插入節(jié)點思路：如果當前共有三個節(jié)點分別是1，2，3，在1和2的中間插入4，原本的指向是1->2 現改變成1->4 4->2 先獲取到指定位置的node，再獲取到前一個位置的node和下一個位置的node
*/
public void insert(int index, E element) {
// 先根據要插入的位置拿到這個位置的節(jié)點對象
Node<E> item = getNode(index);
// 根據插入的元素新建一個節(jié)點
Node<E> eNode = new Node<>(element, null);
// 如果是頭節(jié)點，那么就找不到前一個，直接把這個賦值給head
if (index == 0){
// index==0代表是替換掉頭節(jié)點
this.head = eNode;
eNode.next = item;
this.size++;
}else {
// 根據當前的節(jié)點對象去找到前一個節(jié)點對象和后一個節(jié)點對象
Node<E> before = this.head; // 根據頭節(jié)點去找
for (int i = 0; i < index - 1; i++) {
before = before.next; // 此時的before就是當前節(jié)點的前一個節(jié)點
}
before.next = eNode;
eNode.next = item;
this.size++;
}
}
public static void main(String[] args) {
MySinglyLinkedList<String> list = new MySinglyLinkedList<>();
System.out.println("添加節(jié)點開始------------------------");
list.add((String) "a");
list.add((String) "b");
list.add((String) "c");
list.add((String) "d");
System.out.println("添加節(jié)點完成-------------------------\n");
System.out.println("插入指定的元素");
list.insert(0,"f");
for (int i = 0; i < list.size; i++) {
System.out.println(list.get(i));
}
}
}
雙向鏈表
昨天寫完單向鏈表和棧結構之后，看了看程杰大大的書中有介紹雙向鏈表的部分。雖然是c語言寫的，但是我還是用Java給翻譯出來了。
思路如下：
首先，雙向鏈表和單向鏈表的最大區(qū)別就是，雙向鏈表比單鏈表多了個指向前一節(jié)點的指針。代碼量其實并不比單鏈表多很多，只是思路的轉變需要克服一下。
其次就是在插入元素的時候，我們可以在鏈表的頭部插入，也可以在鏈表的尾部插入（因為有兩個指針嘛）
編碼
代碼其實和單鏈表差不多，如果感興趣的話可以去看看我之前寫的單鏈表的文章。雖然文筆很爛，但是代碼貨真價實。
package com.zxy.lianbiao;
/**
* @Author Zxy
* @Date 2021/2/4 20:11
* @Version 1.0
*/
/**
* 基于雙向鏈表實現元素存取的容器
*
* @param <E>
*/
public class MyDoublyLinkedList<E> implements MyList<E> {
/**
* 定義雙向鏈表節(jié)點對象
*/
class Node<E> {
E item; // 記錄元素
Node<E> prev; // 記錄前一個節(jié)點對象
Node<E> next; // 記錄下一個節(jié)點對象
public Node(Node<E> prev, E item, Node<E> next) {
this.item = item;
this.prev = prev;
this.next = next;
}
}
private Node head; // 記錄頭節(jié)點
private Node tail; // 記錄尾節(jié)點
private int size; // 記錄元素個數
/**
* 向雙向鏈表中添加元素的方法
*
* @param element
*/
@Override
public void add(E element) {
linkLast(element);
}
/**
* 將節(jié)點對象添加到雙向鏈表的尾部
*/
private void linkLast(E element) {
Node t = this.tail; // 獲取尾節(jié)點
Node<E> node = new Node<>(t, element, null); // 創(chuàng)建節(jié)點對象
this.tail = node; // 將新節(jié)點定義為尾節(jié)點 因為原來的尾節(jié)點被這個新節(jié)點替代了
if (t == null) {
// 說明一個節(jié)點都沒有，這個還得是頭節(jié)點
this.head = node;
} else {
t.next = node;
}
this.size++;
}
/**
* 根據指定位置獲取元素
*
* @param index
* @return
*/
@Override
public E get(int index) {
this.checkIndex(index);
// 根據位置查找節(jié)點對象
Node<E> node = this.getNode(index);
return node.item;
}
/**
* 對index的合法性校驗
*/
private void checkIndex(int index) {
if (!(index >= 0 && index < this.size)) {
throw new IndexOutOfBoundsException();
}
}
/**
* 根據位置獲取指定節(jié)點對象
*/
private Node getNode(int index) {
// 判斷當前位置距離頭或者尾哪個節(jié)點更近 使用二分法
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;
}
}
/**
* 返回元素的個數
*
* @return
*/
@Override
public int size() {
return this.size;
}
/**
* 刪除元素
*
* @param index
* @return
*/
@Override
public E remove(int index) {
// 對index進行合法性校驗
this.checkIndex(index);
Node node = this.getNode(index); // 根據位置獲取到節(jié)點對象
// 獲取節(jié)點對象的元素
E item = (E) node.item;
// 判斷當前節(jié)點是否為頭節(jié)點
if (node.prev == null) {
this.head = node.next;
} else {
node.prev.next = node.next;
}
// 判斷當前節(jié)點是否為尾節(jié)點
if (node.next == null) {
// node.prev.next = null;
this.tail = node.prev;
} else {
node.next.prev = node.prev;
}
// 當前節(jié)點斷掉與他后繼節(jié)點的連接
node.next = null;
// 當前節(jié)點斷掉與直接前驅節(jié)點的連接
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é)點對象
Node head = this.head;
Node<E> eNode = new Node<>(null, element, head);
// 將新節(jié)點定義為頭節(jié)點
this.head = eNode;
if (head == null) {
// 如果為空，說明該鏈表中一個節(jié)點都沒有 也就是該頭節(jié)點也是尾節(jié)點
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中實現二叉樹的遍歷與重構,樹是一種非線性的數據結構,它是由n(n>=0)個有限結點組成一個具有層次關系的集合,把它叫做樹是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的,需要的朋友可以參考下2023-10-10
這篇文章主要介紹了Java日期時間類及計算詳解，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下，希望對你的學習有所幫助2022-07-07
Java?深入學習static關鍵字和靜態(tài)屬性及方法
這篇文章主要介紹了Java?深入學習static關鍵字和靜態(tài)屬性及方法，文章通過圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了Java設計模式中備忘錄模式的使用,備忘錄設計模式也叫作快照模式,主要用于實現防丟失、撤銷、恢復等功能,本文將通過示例為大家講解備忘錄模式的定義與使用,需要的同學可以參考一下2024-02-02
這篇文章主要介紹了SpringBoot整合BootStrap實戰(zhàn)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要為大家詳細介紹了java簡單模仿win10計算器de，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了Java NIO ByteBuffer讀取文件方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要給大家介紹了關于Java中方法使用的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-08-08
本文主要介紹了maven配置阿里云倉庫的實現方法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
Spring框架對Java開發(fā)的重要性不言而喻，本文主要介紹了spring DI 依賴注入方式和區(qū)別，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07