Java語言之LinkedList和鏈表的實現(xiàn)方法
一.鏈表概念
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。
邏輯結(jié)構(gòu)：
注：1、如上圖，相當于火車車廂，每一節(jié)都相連在一起。
2、各個結(jié)點連接的方式：通過地址連接，在內(nèi)存當中，相鄰結(jié)點在內(nèi)存中不一定相鄰。
3、所有結(jié)點都在 堆 中申請出來。
4、 每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。
二.鏈表的分類
1.單向、雙向鏈表
注：無論單向還是雙向，都是一個結(jié)點存儲著下（上）一個結(jié)點。
2.帶頭、不帶頭結(jié)點 鏈表
注：無頭和帶頭結(jié)點的主要區(qū)別：有一個起始結(jié)點。
3.循環(huán)、非循環(huán)鏈表
循環(huán)鏈表，就是指：頭、尾結(jié)點有聯(lián)系。
在鏈表結(jié)構(gòu)中，這是主要的鏈表，但是這些鏈表種類還可以結(jié)合，如：帶頭雙向循環(huán)鏈表、雙向循環(huán)鏈表等等。
鏈表的種類很多，但都大同小異，我們主要學習兩種鏈表：
1、無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2、無頭雙向鏈表：在Java的集合框架庫中LinkedList底層實現(xiàn)就是無頭雙向循環(huán)鏈表
三.無頭單向非循環(huán)鏈表的實現(xiàn)
3.1創(chuàng)建簡單鏈表
重點：每個結(jié)點存儲著下一個結(jié)點的地址。
創(chuàng)建鏈表代碼實現(xiàn)：
public class SingleLinkedList {
static class List{
int item; // 存儲數(shù)據(jù)
List next; // 指向下一個結(jié)點
public List(int item) {
this.item = item;
}
public List() {};
}
//各種鏈表實現(xiàn)方法
//頭插法
public void addFirst(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index,int data){
}
//查找是否包含關(guān)鍵字key是否在單鏈表當中
public boolean contains(int key){
return false;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
public void remove(int key){
}
//得到單鏈表的長度
public int size(){
return -1;
}
//鏈表的清空
public void clear() {
}
//展示鏈表
public void display() {}3.2 鏈表基本方法實現(xiàn)
1.遍歷鏈表元素
public void show() {
//這里不是定義了一個節(jié)點 這里只是一個引用
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}2.獲取鏈表長度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}3.查詢數(shù)據(jù)
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
//如果val值 是引用類型 那么這里得用equals來進行比較！??！
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}4.鏈表的清空
public void clear() {
//將所有結(jié)點都置空，更為安全
while (head != null) {
ListNode headNext = head.next;
head.next = null;
head = headNext;
}
}3.3四大基本功能
3.3.1 、增加元素結(jié)點
1.頭插法：將新增結(jié)點放在鏈表的頭部。
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}2.尾插法：將新增結(jié)點直接連接在鏈表的尾部
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
//cur 指向的節(jié)點就是尾巴節(jié)點
cur.next = node;
}3.選擇下標值，添加結(jié)點
public void addIndex(int index,int data){
int len = size();
//0、判斷index位置的合法性
if(index < 0 || index > len) {
throw new IndexOutOfBounds("任意位置插入數(shù)據(jù)的時候，index位置不合法: "+index);
}
if(index == 0) {
addFirst(data);
return;
}
if(index == len) {
addLast(data);
return;
}
//1、先找到index-1位置的節(jié)點
ListNode cur = findIndex(index);
//2、進行插入
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}3.3.2.查找元素結(jié)點
查找一個元素，返回對應(yīng)的下標值。
public ListNode findIndex(int index) {
ListNode cur = head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;//index-1位置的節(jié)點
}3.3.3.刪除元素結(jié)點
先找到對應(yīng)的下標值，然后進行刪除。刪除方法，前一個結(jié)點連接到刪除結(jié)點的后一個結(jié)點。
如圖，先斷開d2與d3的連接，然后d2直接連接d4
代碼實現(xiàn)：
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
public void remove(int key){
if(head == null) {
return;
}
//當刪除結(jié)點為頭結(jié)點
if(head.val == key) {
head = head.next;
return;
}
ListNode prev = searchPrev(key); //返回待刪除結(jié)點的前一個結(jié)點
if(prev == null) {
System.out.println("沒有這個數(shù)據(jù)！");
return;
}
ListNode del = prev.next;
prev.next = del.next;
}
private ListNode searchPrev(int key) {
ListNode prev = head;
while (prev.next != null) {
if(prev.next.val == key) {
return prev;
}else {
prev = prev.next;
}
}
return null;
}3.3.4.結(jié)點信息修改
修改指定下標值的結(jié)點元素
public void searchPrev(int num,int date) {
ListNode prev = head;
for(int i=0;i<num-1;i++) {
prev = prev.next;
}
prev.val=date;
}四.LinkedList是什么？
LinkedList的底層是雙向鏈表結(jié)構(gòu)，由于鏈表沒有將元素存儲在連續(xù)的空間中，元素存儲在單獨的節(jié)點中，然后通過引用將節(jié)點連接起來了，因此在在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。
如圖所示：1. LinkedList實現(xiàn)了List接口
2. LinkedList的底層使用了雙向鏈表
3. LinkedList沒有實現(xiàn)RandomAccess接口，因此LinkedList不支持隨機訪問。
4. LinkedList的任意位置插入和刪除元素時效率比較高，時間復雜度為O(1)
5. LinkedList比較適合任意位置插入的場景
五.LinkedList使用方法
| 方法 | 解釋 | |
| 構(gòu)造方法 | LinkedList() | 無參構(gòu)造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器中元素構(gòu)造List | |
| 常用方法 | boolean add(E e) | 尾插e |
| void add(int index,E element) | 將e插入到index位置 | |
| boolean addAII(Collection<? extends E> c) | 尾插c中的元素 | |
| E remove(int index) | 刪除index位置元素 | |
| boolean remove(Object o) | 刪除遇到的第一個o | |
| E get( int index) | 獲取下標index位置元素 | |
| void clear() | 清空 |
總結(jié)
到此這篇關(guān)于Java語言之LinkedList和鏈表的實現(xiàn)方法的文章就介紹到這了,更多相關(guān)Java LinkedList和鏈表實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
IntelliJ Idea 2020.1 正式發(fā)布,官方支持中文（必看）
這篇文章主要介紹了IntelliJ Idea 2020.1 正式發(fā)布，官方支持中文了,本文通過截圖的形式給大家展示，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-04
所有與該configuration 對象關(guān)聯(lián)的模版實例都就可以通過獲得to_upper 轉(zhuǎn)換器，company 來獲得字符串，因此你不需要再一次次的往root 中添加這些變量了。如果你往root 添加同名的變量，那么你新添加的變量將會覆蓋之前的共享變量。2016-04-04
一個applicationContext 加載錯誤導致的阻塞問題及解決方法
這篇文章主要介紹了一個applicationContext 加載錯誤導致的阻塞問題及解決方法,需要的朋友可以參考下2018-11-11
這篇文章主要介紹了Java編程中避免equals方法的隱藏陷阱介紹，具有一定參考價值，需要的朋友可以了解下。2017-11-11
SpringBoot可視化接口開發(fā)工具magic-api的簡單使用教程
作為Java后端開發(fā)，平時開發(fā)API接口的時候經(jīng)常需要定義Controller、Service、Dao、Mapper、XML、VO等Java對象。有沒有什么辦法可以讓我們不寫這些代碼，直接操作數(shù)據(jù)庫生成API接口呢？今天給大家推薦一款工具magic-api，來幫我們實現(xiàn)這個小目標！2021-06-06
解決idea啟動報錯javax.imageio.IIOException的問題
這篇文章主要介紹了idea啟動報錯javax.imageio.IIOException，解決打不開idea問題,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
這篇文章主要介紹了Java滾動數(shù)組計算編輯距離操作,涉及java字符串與數(shù)組的遍歷、計算、轉(zhuǎn)換等相關(guān)操作技巧,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了Netty進階之ChannelPoolMap源碼解析,ChannelPoolMap是用來存儲ChannelPool和指定key的一個集合Map,實際的應(yīng)用場景就是服務(wù)器端是一個分布式集群服務(wù),擁有多個配置地址,這樣我們就可以配置多個服務(wù)地址,減輕單臺服務(wù)器的壓力,需要的朋友可以參考下2023-11-11
Spring Boot 配置和使用多線程池的實現(xiàn)
這篇文章主要介紹了Spring Boot 配置和使用多線程池的實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-06-06
多態(tài)性是對象多種表現(xiàn)形式的體現(xiàn)。在面向?qū)ο笾?，最常見的多態(tài)發(fā)生在使用父類的引用來引用子類的對象。下面這篇文章主要給大家深入的介紹了Java三大特性中多態(tài)的相關(guān)資料，有需要的朋友可以參考借鑒，下面來一起看看吧。2017-01-01