Java數(shù)據(jù)結(jié)構(gòu)（線性表）詳解
更新時(shí)間：2017年01月24日 08:45:46 作者：%陽(yáng)陽(yáng)羊%
本文主要介紹了Java數(shù)據(jù)結(jié)構(gòu)（線性表）的相關(guān)知識(shí)。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧
線性表的鏈?zhǔn)酱鎯?chǔ)與實(shí)現(xiàn)
實(shí)現(xiàn)線性表的另一種方法是鏈?zhǔn)酱鎯?chǔ)，即用指針將存儲(chǔ)線性表中數(shù)據(jù)元素的那些單元依次串聯(lián)在一起。這種方法避免了在數(shù)組中用連續(xù)的單元存儲(chǔ)元素的缺點(diǎn)，因而在執(zhí)行插入或 刪除運(yùn)算時(shí)，不再需要移動(dòng)元素來(lái)騰出空間或填補(bǔ)空缺。然而我們?yōu)榇烁冻龅拇鷥r(jià)是，需要在每個(gè)單元中設(shè)置指針來(lái)表示表中元素之間的邏輯關(guān)系，因而增加了額外的存儲(chǔ)空間的開銷.
單鏈表
鏈表是一系列的存儲(chǔ)數(shù)據(jù)元素的單元通過(guò)指針串接起來(lái)形成的，因此每個(gè)單元至少有兩個(gè)域，一個(gè)域用于數(shù)據(jù)元素的存儲(chǔ)，另一個(gè)域是指向其他單元的指針。這里具有一個(gè)數(shù)據(jù)域和多個(gè)指針域的存儲(chǔ)單元通常稱為結(jié)點(diǎn)（node）.
結(jié)點(diǎn)接口
package com.wjy.Data_Structure.linearlist.common;
public interface Node {
/**
* 獲取結(jié)點(diǎn)數(shù)據(jù)域
*
* @return
*/
public Object getData();
/**
* 設(shè)置結(jié)點(diǎn)數(shù)據(jù)域
*
* @param obj
*/
public void setData(Object obj);
}
單鏈表結(jié)點(diǎn)定義
package com.wjy.Data_Structure.linearlist.common;
//單鏈表結(jié)點(diǎn)定義
public class SLNode implements Node {
private Object element;
private SLNode next;
public SLNode() {
}
public SLNode(Object ele, SLNode next) {
this.element = ele;
this.next = next;
}
public SLNode getNext() {
return next;
}
public void setNext(SLNode next) {
this.next = next;
}
/******** Methods of Node Interface **********/
@Override
public Object getData() {
return element;
}
@Override
public void setData(Object obj) {
element = obj;
}
}
線性表的單鏈表實(shí)現(xiàn)
在使用單鏈表實(shí)現(xiàn)線性表的時(shí)候，為了使程序更加簡(jiǎn)潔，我們通常在單鏈表的前面添 加一個(gè)啞元結(jié)點(diǎn)，也稱為頭結(jié)點(diǎn)。在頭結(jié)點(diǎn)中不存儲(chǔ)任何實(shí)質(zhì)的數(shù)據(jù)對(duì)象，其 next 域指向 線性表中 0 號(hào)元素所在的結(jié)點(diǎn)，頭結(jié)點(diǎn)的引入可以使線性表運(yùn)算中的一些邊界條件更容易處理。
package com.wjy.Data_Structure.linearlist.listslinkimpl;
import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;
import com.wjy.Data_Structure.linearlist.common.List;
import com.wjy.Data_Structure.linearlist.common.SLNode;
import com.wjy.Data_Structure.linearlist.common.Strategy;
import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;
//線性表的單鏈表實(shí)現(xiàn)
public class ListSLinked implements List {
private Strategy strategy; // 數(shù)據(jù)元素比較策略
private SLNode head; // 單鏈表首結(jié)點(diǎn)引用
private int size;// 線性表中數(shù)據(jù)元素的個(gè)數(shù)
public ListSLinked() {
this(new DefaultStrategy());
}
public ListSLinked(Strategy strategy) {
this.strategy = strategy;
head = new SLNode();
size = 0;
}
/**
* 輔助方法： 獲取數(shù)據(jù)元素 e 所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
*
* @param e
* @return
*/
private SLNode getPreNode(Object e) {
SLNode p = head;
while (p.getNext() != null)
if (strategy.equal(p.getNext().getData(), e))
return p;
else
p = p.getNext();
return null;
}
/**
* 輔助方法： 獲取序號(hào)為 0<=i<size 的元素所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
*
* @param i
* @return
*/
private SLNode getPreNode(int i) {
SLNode p = head;
for (; i > 0; i--)
p = p.getNext();
return p;
}
/**
* 輔助方法： 獲取序號(hào)為 0<=i<size 的元素所在結(jié)點(diǎn)
*
* @param i
* @return
*/
private SLNode getNode(int i) {
SLNode p = head.getNext();
for (; i > 0; i--)
p = p.getNext();
return p;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object e) {
return indexOf(e) != -1;
}
@Override
public int indexOf(Object e) {
SLNode p = head.getNext();
int index = 0;
while (p != null)
if (strategy.equal(p.getData(), e)) {
return index;
} else {
index++;
p = p.getNext();
}
return -1;
}
@Override
public void insert(int i, Object e) throws OutOfBoundaryException {
if (i < 0 || i > size)
throw new OutOfBoundaryException("錯(cuò)誤，指定的插入序號(hào)越界");
SLNode p = getPreNode(i);
SLNode q = new SLNode(e, p.getNext());
p.setNext(q);
size++;
return;
}
@Override
public boolean insertBefore(Object obj, Object e) {
SLNode p = getPreNode(obj);
if (p != null) {
SLNode q = new SLNode(e, p.getNext());
p.setNext(q);
size++;
return true;
}
return false;
}
@Override
public boolean insertAfter(Object obj, Object e) {
SLNode p = head.getNext();
while (p != null)
if (strategy.equal(p.getData(), obj)) {
SLNode q = new SLNode(e, p.getNext());
p.setNext(q);
size++;
return true;
} else {
p = p.getNext();
}
return false;
}
@Override
public Object remove(int i) throws OutOfBoundaryException {
if (i < 0 || i >= size)
throw new OutOfBoundaryException("錯(cuò)誤，指定的刪除序號(hào)越界。");
SLNode p = getPreNode(i);
Object obj = p.getNext().getData();
p.setNext(p.getNext().getNext());
size--;
return obj;
}
@Override
public boolean remove(Object e) {
SLNode p = getPreNode(e);
if (p != null) {
p.setNext(p.getNext().getNext());
size--;
return true;
}
return false;
}
@Override
public Object replace(int i, Object e) throws OutOfBoundaryException {
if (i < 0 || i >= size)
throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。");
SLNode p = getNode(i);
Object obj = p.getData();
p.setData(e);
return obj;
}
@Override
public Object get(int i) throws OutOfBoundaryException {
if (i < 0 || i >= size)
throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。");
SLNode p = getNode(i);
return p.getData();
}
}
簡(jiǎn)單的測(cè)試用例
package com.wjy.Data_Structure.linearlist.listslinkimpl;
import org.junit.Test;
import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;
public class ListSLinkedTest {
@Test
public void testInsert() {
ListSLinked list = new ListSLinked();
for (int i = 0; i < 10; i++) {
list.insert(i, i + 1);
}
System.out.println("刪除：" + list.remove(0));
System.out.println(list.contains(1));
list.insertBefore(2, 100);
list.insertAfter(2, 101);
list.replace(list.getSize() - 1, 1000);
for (int i = 0; i < list.getSize(); i++) {
System.out.println(list.get(i));
}
}
}
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)代碼倉(cāng)庫(kù)：
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，同時(shí)也希望多多支持腳本之家！
相關(guān)文章
JAVA中 終止線程的方法介紹，需要的朋友可以參考一下2013-03-03
Spring Boot集群管理工具KafkaAdminClient使用方法解析
這篇文章主要介紹了Spring Boot集群管理工具KafkaAdminClient使用方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-02-02
HashMap 作為 Java 中最常用的數(shù)據(jù)結(jié)構(gòu)之一，用于存儲(chǔ)和管理鍵值對(duì)，HashMap 基于哈希函數(shù)實(shí)現(xiàn)，能通過(guò)將 key 映射到特定的位置來(lái)實(shí)現(xiàn)快速存儲(chǔ)、查找和刪除數(shù)據(jù)，接下來(lái)將從源碼角度分析以通俗易懂的方式向大家講解一下 HashMap 如何確定 key 的存儲(chǔ)位置的2023-07-07
利用SpringBoot實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式總結(jié)
關(guān)于動(dòng)態(tài)數(shù)據(jù)源的切換的方案有很多,核心只有兩種,一種是構(gòu)建多套環(huán)境,另一種是基于spring原生的AbstractRoutingDataSource切換,這篇文章主要給大家介紹了關(guān)于利用SpringBoot實(shí)現(xiàn)多數(shù)據(jù)源的兩種方式,需要的朋友可以參考下2021-10-10
這篇文章主要介紹了Spring使用redis遇到的問(wèn)題及解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
jdbc+jsp實(shí)現(xiàn)簡(jiǎn)單員工管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了jdbc+jsp實(shí)現(xiàn)簡(jiǎn)單員工管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-02-02
這篇文章主要介紹了spring mvc路徑匹配原則詳解，小編覺得還是挺不錯(cuò)的，這里分享給大家，需要的朋友可以參考下，下面就和小編一起來(lái)看看吧2018-02-02
springboot config 攔截器使用方法實(shí)例詳解
本文介紹Spring-Boot中使用攔截器的相關(guān)知識(shí)，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友參考下吧2018-05-05
這篇文章主要介紹了javascript最新2020經(jīng)典面試題的相關(guān)內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2020-02-02
這篇文章主要介紹了Java Method類及invoke方法原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08