Java全面講解順序表與鏈表的使用
更新時間：2022年05月07日 14:12:39 作者：菜菜不恰菜
大家好，今天給大家?guī)淼氖琼樞虮砗玩湵?，我覺得順序表還是有比較難理解的地方的，于是我就把這一塊的內(nèi)容全部整理到了一起，希望能夠給剛剛進行學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人帶來一些幫助，或者是已經(jīng)學(xué)過這塊的朋友們帶來更深的理解，我們現(xiàn)在就開始吧
線性表
線性表 （ linear list ） 是 n 個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見 的線性表：順序表、鏈表、棧、隊列、字符串 ... 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)（內(nèi)存上）上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組（在物理上是連續(xù)的）和鏈?zhǔn)浇Y(jié)構(gòu)（在物理上不連續(xù)）的形式存儲。
順序表
順序表是用一段 物理地址連續(xù) 的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。（可以說順序表就相當(dāng)于一個數(shù)組）
那么問題來了，為什么不直接使用數(shù)組，而要把數(shù)組放在類當(dāng)中，然后再對數(shù)組進行操作？ 因為數(shù)組沒有面向?qū)ο螅褦?shù)組放進類當(dāng)中，可通過對象對它進行操作。
聽著概念有點模糊，接下來通過模擬順序表的接口實現(xiàn)來認(rèn)識一下順序表：
??用Arraylist來模擬實現(xiàn)順序表ArrayList的接口實現(xiàn)：
Arraylist:
public class Arraylist{
public int[] arr;
public int useSize;//數(shù)組有效個數(shù)
public Arraylist() {
this.arr = new int[10];//假設(shè)數(shù)組長度為10
}
//打印順序表
public void display() {
for (int i = 0; i < this.useSize; i++) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}
public boolean isFull() {
return this.arr.length == this.useSize;
}
// 在 pos 位置新增元素
public void add(int pos, int date) {
if (pos < 0 || pos > useSize) {
System.out.println("pos位置不合法"+" ");
return;
}
if (isFull()) {
this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
}
for (int i = this.useSize - 1; i >= pos; i--) {
this.arr[i + 1] = this.arr[i];
}
this.arr[pos] = date;
this.useSize++;
}
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int i = 0; i < this.useSize; i++) {
if (arr[i] == toFind) {
return true;
}
}
return false;
}
// 查找某個元素對應(yīng)的位置
public int search(int toFind) {
for (int i = 0; i < this.useSize; i++) {
if (arr[i] == toFind) {
return i;
}
}
return -1;
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >=useSize){
System.out.println("pos位置不合法"+" ");
return -1;//萬一順序表中有-1這個元素怎么辦，后期說
}
if(isEmpty()){
System.out.print("順序表為空");
return -1;
}
for (int i = 0; i < this.useSize; i++) {
if (i == pos) {
return this.arr[i];
}
}
return -1;
}
public boolean isEmpty(){
return this.useSize==0;
}
// 給 pos 位置的元素設(shè)為 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >=useSize){
System.out.print("pos位置不合法"+" ");
return;
}
if(isEmpty()){
System.out.println("順序表為空");
return;
}
this.arr[pos] = value;
}
//刪除第一次出現(xiàn)的關(guān)鍵字key
public void remove(int toRemove){
if(isEmpty()) {//判斷順序表是否為空
System.out.println("順序表為空");
}
int x=search(toRemove);
if(x==-1){
System.out.println("沒有你要刪除的數(shù)字");
return;
}
for (int j = x; j<=this.useSize-1; j++) {
this.arr[j]=this.arr[j+1];
}
this.useSize--;
}
//清空順序表
public void clear() {
this.usedSize = 0;
}
}在pos位置新增元素：
判斷是否包含某個元素：
查找pos位置：
在pos位置上給值value
刪除第一次出現(xiàn)的關(guān)鍵字key
鏈表
鏈表是一種 物理存儲結(jié)構(gòu)(內(nèi)存）上非連續(xù) 存儲結(jié)構(gòu)，數(shù)據(jù)元素的 邏輯順序 是通過鏈表中的 引用鏈接 次序?qū)崿F(xiàn)的 。 實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有 8 種鏈表結(jié)構(gòu)：
單向、雙向
帶頭、不帶頭
循環(huán)、非循環(huán)
接下來主要講兩種：單向不帶頭非循環(huán)、雙向不帶頭非循環(huán)
??鏈表接口的模擬實現(xiàn)（ 單向不帶頭非循環(huán)）： 鏈表是由一個一個節(jié)點組成，單向不帶頭非循環(huán)鏈表每個節(jié)點有兩個域，一個是數(shù)據(jù)域，用來存放數(shù)據(jù)，另一個是存放下一個節(jié)點的地址。
class ListNode{//創(chuàng)建節(jié)點,鏈表是由一個一個節(jié)點組成，每個節(jié)點有兩個域組成，數(shù)據(jù)域和下一個節(jié)點地址組成
public int val;
public ListNode next;//沒有初始化默認(rèn)為null
public ListNode(int val){
this.val=val;
}
}
//模擬實現(xiàn)單向不帶頭非循環(huán)鏈表的接口實現(xiàn)，用MyLinkedList模擬實現(xiàn)LinkedList
public class MyLinkedList {
public ListNode head;//創(chuàng)建頭節(jié)點
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(88);
ListNode listNode3 = new ListNode(36);
listNode1.next = listNode2;
listNode2.next = listNode3;
this.head = listNode1;//頭節(jié)點為第一個節(jié)點地址
}
public void display() {
ListNode cur;
cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode cur = this.head;
if (cur == null) {
this.head = node;
} else {
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
//找到index-1下標(biāo)位置
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
public void addIndex(int index, int data) {
if(index<0||index>size()){
System.out.println("輸入位置不合法");
return;
}
if(index==0){//頭插
this.addFirst(data);
return;
}
if(index==size()){//尾插
this.addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
public boolean contains(int key) {
return false;
}
public ListNode findremove(int key){
ListNode cur=this.head.next;
while(cur!=null) {
if (cur.next.val == key) {
return cur;
} else {
cur=cur.next;
}
}
return null;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
public void remove(int key) {
if (this.head == null) {
System.out.println("鏈表為空");
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = findremove(key);//找到關(guān)鍵字上一個節(jié)點所在位置，并返回該節(jié)點
if (cur == null) {
System.out.println("沒找到關(guān)鍵字");
return;
}
ListNode del=cur.next;
cur.next=del.next;
return;
}
//刪除所有值為key的節(jié)點
public ListNode removeAllKey(int key) {
if(this.head==null){
return null;
}
ListNode per=this.head;
ListNode cur=this.head.next;
while(cur!=null){
if(cur.val==key){
per.next=cur.next;
cur=cur.next;
}
else{
per=cur;
cur=cur.next;
}
}
if(this.head.val==key){
this.head=this.head.next;
}
return this.head;
}
//得到單鏈表的長度
public int size() {
ListNode cur=this.head;
int count=0;
while (cur!=null){
count++;
cur=cur.next;
}
return count;
}
//清除鏈表
public void clear() {
//this.head=null;//簡單粗暴寫法，當(dāng)一個節(jié)點沒有被指向時，就沒意義了
//遍歷
while(this.head!=null){
ListNode curNext=this.head.next;
this.head.next=null;
this.head=curNext;
}
}
}創(chuàng)建節(jié)點：
以上說的鏈表是指單向不帶頭非循環(huán)鏈表?。。?/p>
初始化鏈表：
打印鏈表：
頭插法：
尾插法：
任意位置插入一個數(shù)據(jù)：
刪除關(guān)鍵字key所在節(jié)點位置：
刪除所有值為key的節(jié)點：
雙向不帶頭非循環(huán)：
這種鏈表至少有三個域組成，一個是數(shù)據(jù)域，一個是存放上一個節(jié)點的位置，一個存放下一個節(jié)點的位置，雙向比單向的好處就體現(xiàn)出來了，雙向鏈表只要知道當(dāng)前節(jié)點位置，就可以對鏈表進行增刪查改，而單相鏈表還需要知道當(dāng)前節(jié)點的上一個節(jié)點。
接口模擬實現(xiàn)：
//雙向不帶頭非循環(huán)
//創(chuàng)建節(jié)點
class ListNode{
int val;
ListNode prev;//前一個節(jié)點地址
ListNode next;//下一個節(jié)點地址
public ListNode(int val){
this.val=val;
}
}
public class myLinkedList {
public ListNode head;//頭節(jié)點
public ListNode last;//尾節(jié)點
//得到雙向鏈表長度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;//如果鏈表為空。返回0，所以這里可再單獨判斷也可不單獨判斷
}
//打印雙向鏈表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含關(guān)鍵字在鏈表中
public boolean contain(int key) {
if (this.head == null) {
return false;
}
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//刪除第一次出現(xiàn)的關(guān)鍵字
public void remove(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {//第一種：關(guān)鍵字是在頭節(jié)點
this.head = this.head.next;
if (this.head != null) {
head.prev = null;
} else {//如果鏈表為空1情況下，要保證最后一個節(jié)點也要為空
this.last = null;
}
} else {//第二種情況：關(guān)鍵字在中間或者結(jié)尾
cur.prev.next = cur.next;
if (cur.next != null) {//中間
cur.next.prev = cur.prev;
} else {
last = cur.prev;//結(jié)尾
}
}
return;
}
cur=cur.next;
}
}
//刪除所有值為key的節(jié)點
public void removeAllkey(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {//第一種：關(guān)鍵字是在頭節(jié)點
this.head = cur.next;
if (this.head != null) {
cur.next.prev = null;
} else {//如果鏈表為空1情況下，要保證最后一個節(jié)點也要為空
this.last = null;
}
} else {//第二種情況：關(guān)鍵字在中間或者結(jié)尾
cur.prev.next = cur.next;
if (cur.next!=null) {//中間
cur.next.prev = cur.prev;
}
last = cur.prev;//結(jié)尾
}
}
cur=cur.next;
}
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
this.last = node;
}
else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node=new ListNode(data);
if(this.head==null) {
this.head = node;
this.last = node;
}
this.last.next=node;
node.prev=this.last;
this.last=node;
}
//任意位置插入，第一個數(shù)據(jù)節(jié)點下標(biāo)為0
public ListNode search(int index){//尋找插入的位置
ListNode cur=this.head;
while(index!=0){
cur=cur.next;
index--;
}
return cur;
}
public void addIndex(int index,int data){
ListNode node=new ListNode(data);
if(index<0||index>size()){
System.out.println("坐標(biāo)違法");
return;
}
if(index==0){
addFirst(data);
return;
}
if(index==size()){
addLast(data);
return;
}
ListNode cur=search(index);
node.next=cur.prev.next;
cur.prev.next=node;
node.prev=cur.prev;
cur.prev=node;
return;
}
//清除鏈表
public void clear(){
while(this.head!=null){
ListNode curNext=this.head.next;
this.head.prev=null;
this.head.next=null;
this.head=curNext;
}
last=null;
}
}查找是否包含關(guān)鍵字在鏈表中：
刪除第一次出現(xiàn)的關(guān)鍵字：
刪除所有值為key的節(jié)點：
頭插法：
尾插法：
任意位置插入，第一個數(shù)據(jù)節(jié)點下標(biāo)為0：
小結(jié)
在這里，我們講了順序表也講了鏈表，那么他們有什么區(qū)別呢？
在組織上：
1、順序表底層是一個數(shù)組，他是一個邏輯上和物理上都是連續(xù)的
2、鏈表是一個由若干節(jié)點組成的一個數(shù)據(jù)結(jié)構(gòu)，邏輯上是連續(xù)的但是在物理上[內(nèi)存上]是不連續(xù)的。
在操作上：
1、順序表適合，查找相關(guān)的操作，因為，可以使用下標(biāo)，直接獲取到某個位置的元素。
2、鏈表適合于,頻繁的插入和刪除操作。此時不需要像順序表一樣,移動元素。鏈表的插入只需要修改指向即可。
3、順序表還有不好的地方，就是你需要看滿不滿，滿了要擴容，擴容了之后，不一定都能放完。所以，他的空間上的利用率不高。
以上就是我對順序表和鏈表的一些理解，如果有什么不對的地方，歡迎各位提出來！
到此這篇關(guān)于Java全面講解順序表與鏈表的使用 的文章就介紹到這了,更多相關(guān)Java順序表與鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了spring mvc請求controller訪問方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了Spinrg WebFlux中Cookie的讀寫的示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了Java的內(nèi)存分配與回收策略詳解,對象的內(nèi)存分配，就是在堆上分配,對象主要分配在新生代的 Eden 區(qū)上，少數(shù)情況下可能直接分配在老年代，分配規(guī)則不固定，取決于當(dāng)前使用的垃圾收集器組合以及相關(guān)的參數(shù)配置,需要的朋友可以參考下2023-08-08
java之CSV大批量數(shù)據(jù)入庫的實現(xiàn)
本文主要介紹了java之CSV大批量數(shù)據(jù)入庫的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
Java中構(gòu)造方法set/get和toString的使用詳解
這篇文章主要介紹了Java中構(gòu)造方法set/get和toString的使用詳解，構(gòu)造函數(shù)的最大作用就是創(chuàng)建對象時完成初始化，當(dāng)我們在new一個對象并傳入?yún)?shù)的時候，會自動調(diào)用構(gòu)造函數(shù)并完成參數(shù)的初始化,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了mybatis sql的括號問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01
java利用注解實現(xiàn)簡單的excel數(shù)據(jù)讀取
這篇文章主要為大家詳細(xì)介紹了java利用注解實現(xiàn)簡單的excel數(shù)據(jù)讀取，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
關(guān)于Springboot數(shù)據(jù)庫配置文件明文密碼加密解密的問題
這篇文章主要介紹了Springboot數(shù)據(jù)庫配置文件明文密碼加密解密的問題，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-03-03
本篇文章主要對Java中的設(shè)計模式如，創(chuàng)建型模式、結(jié)構(gòu)型模式和行為型模式以及7大原則進行了歸納整理，需要的朋友可以參考下,希望能給你帶來幫助2021-07-07
詳解IDEA中類加載器調(diào)用getResourceAsStream()方法需注意的問題
這篇文章主要介紹了詳解IDEA中類加載器調(diào)用getResourceAsStream()方法需注意的問題，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02