Java數(shù)據(jù)結(jié)構(gòu)之鏈表相關(guān)知識(shí)總結(jié)
更新時(shí)間：2021年06月18日 16:25:22 作者：weixin_42280618
今天給大家?guī)黻P(guān)于Java數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí),文章圍繞Java鏈表展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下
一、鏈表
1.1 概述
鏈表是真正動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，最簡單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，基本用于輔助組成其他數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)存儲(chǔ)在“節(jié)點(diǎn)”（Node）中
優(yōu)點(diǎn)：真正的動(dòng)態(tài)，不需要處理固定容量的問題
缺點(diǎn)：喪失了隨機(jī)訪問的能力
1.2 鏈表使用的基本功能
定義Node節(jié)點(diǎn)
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
向鏈表中添加元素
具體代碼實(shí)現(xiàn)：
//向鏈表中間添加元素
//在鏈表的index(0-based)位置添加新的元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed.Illeagl failed.");
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size++;
}
向鏈表中刪除元素
具體代碼實(shí)現(xiàn)：
//鏈表中刪除index(0-based)位置的元素，返回刪除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed.Illeagl failed.");
Node pre = dummyHead;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
Node retNode = pre.next;
pre.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
鏈表功能的實(shí)現(xiàn)及測試類
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node(null, null);
size = 0;
}
//獲取鏈表中的元素個(gè)數(shù)
public int getSize(){
return size;
}
//返回鏈表是否為空
public boolean isEmpty(){
return size == 0;
}
//向鏈表頭添加元素
public void addFirst(E e){
// Node node = new Node(e);
// node.next = head;
// head = node;
add(0, e);
}
//向鏈表中間添加元素
//在鏈表的index(0-based)位置添加新的元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed.Illeagl failed.");
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size++;
}
//在鏈表的末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
//獲得鏈表的第index(0-based)個(gè)位置的元素
//在鏈表中不是一個(gè)常用的操作
public E get(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed.Illeagl failed.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
//獲得鏈表的第一個(gè)元素
public E getFirst(){
return get(0);
}
//獲得鏈表的最后一個(gè)元素
public E getLast(){
return get(size - 1);
}
//修改鏈表的第index(0-based)個(gè)位置的元素
//在鏈表中不是一個(gè)常用的操作
public void set(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed.Illeagl failed.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
//查找鏈表中是否有元素e
public boolean contains(E e){
Node cur = dummyHead.next;
while(cur != null){
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
//鏈表中刪除index(0-based)位置的元素，返回刪除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed.Illeagl failed.");
Node pre = dummyHead;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
Node retNode = pre.next;
pre.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
//從鏈表中刪除第一個(gè)元素
public E removeFirst(){
return remove(0);
}
//從鏈表中刪除最后一個(gè)元素
public E removeLast(){
return remove(size - 1);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
// Node cur = dummyHead.next;
// while (cur != null){
// res.append(cur + "->");
// cur = cur.next;
// }
for (Node cur = dummyHead.next; cur != null; cur = cur.next){
res.append(cur + "->");
}
res.append("null");
return res.toString();
}
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 5; i++) {
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(2, 666);
System.out.println(linkedList);
linkedList.remove(2);
System.out.println(linkedList);
linkedList.removeFirst();
System.out.println(linkedList);
linkedList.removeLast();
System.out.println(linkedList);
}
}
二、鏈表實(shí)現(xiàn)棧操作
使用第二章中的棧接口，創(chuàng)建第一節(jié)中的鏈表實(shí)現(xiàn)對象，實(shí)現(xiàn)棧的操作，具體如下：
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
public LinkedListStack(){
list = new LinkedList<>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E value) {
list.addFirst(value);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack : top");
res.append(list);
return res.toString();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
三、鏈表實(shí)現(xiàn)隊(duì)列操作
使用第二章中的隊(duì)列接口，創(chuàng)建無頭節(jié)點(diǎn)的鏈表實(shí)現(xiàn)隊(duì)列操作，具體如下：
public class LinkedListQueue<E> implements Queue<E> {
private class Node{
public E e;
public LinkedListQueue.Node next;
public Node(E e, LinkedListQueue.Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head,tail;
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) {
if(tail == null){
tail = new Node(e);
head = tail;
}else{
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
if (isEmpty())
throw new IllegalArgumentException("Cannot dequeue form any empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null)
tail = null;
return retNode.e;
}
@Override
public E getFront() {
if (isEmpty())
throw new IllegalArgumentException("Cannot getFront form any empty queue.");
return head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue : front ");
Node cur = head;
while (cur != null){
res.append(cur + "->");
cur = cur.next;
}
res.append("Null tail");
return res.toString();
}
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表相關(guān)知識(shí)總結(jié)的文章就介紹到這了,更多相關(guān)Java鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
基于Docker的K8s(Kubernetes)集群部署方案
這篇文章主要介紹了基于Docker的K8s(Kubernetes)集群部署方案,文中介紹了安裝k8s的可視化界面的相關(guān)操作，需要的朋友可以參考下2024-01-01
java去除空格、標(biāo)點(diǎn)符號的方法實(shí)例
這篇文章主要給大家介紹了關(guān)于java去除空格、標(biāo)點(diǎn)符號的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
解決SpringCloud?Feign異步調(diào)用傳參問題
這篇文章主要介紹了SpringCloud?Feign異步調(diào)用傳參問題,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-05-05
基于java語言實(shí)現(xiàn)快遞系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了基于java語言實(shí)現(xiàn)快遞系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了jasypt dubbo配置密文存放使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
應(yīng)用Java泛型和反射導(dǎo)出CSV文件的方法
這篇文章主要介紹了應(yīng)用Java泛型和反射導(dǎo)出CSV文件的方法,通過一個(gè)自定義函數(shù)結(jié)合泛型與反射的應(yīng)用實(shí)現(xiàn)導(dǎo)出CSV文件的功能,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-12-12
RestTemplate發(fā)送form-data請求上傳rul資源文件及對象參數(shù)方式
這篇文章主要介紹了RestTemplate發(fā)送form-data請求上傳rul資源文件及對象參數(shù)方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
Springboot配置文件內(nèi)容加密代碼實(shí)例
這篇文章主要介紹了Springboot配置文件內(nèi)容加密代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
深入解析Java的設(shè)計(jì)模式編程中單例模式的使用
這篇文章主要介紹了深入解析Java的設(shè)計(jì)模式編程中單例模式的使用,一般來說將單例模式分為餓漢式單例和懶漢式單例,需要的朋友可以參考下2016-02-02
這篇文章主要介紹了springboot與dubbo的版本匹配問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10