Java實現(xiàn)線性表的鏈式存儲
更新時間：2020年10月29日 15:47:44 作者：I like study.
這篇文章主要為大家詳細介紹了Java實現(xiàn)線性表的鏈式存儲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了Java實現(xiàn)線性表的鏈式存儲，供大家參考，具體內容如下
鏈表：一種物理存儲結構上非連續(xù)、非順序的存儲結構,數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。
package algorithm.datastructure.linklist;
import java.util.NoSuchElementException;
/*
* 鏈表
* 物理存儲上非連續(xù)的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)
*
* */
public class LinkedList {
private Node head;//頭節(jié)點
private int size;//鏈表長度
static private class Node{
private int data;
private Node next;
public Node(){
}
private Node(int data,Node next){
this.data=data;
this.next=next;
}
}
//初始化空鏈表
public LinkedList(){
//head=null;
}
//添加元素
public Boolean add(int element){
linkLast(element);
return true;
}
//在某個位置之前添加元素
public Boolean add(int index,Integer element){
checkPositionIndex(index);
if (index==size){
linkLast(element);
} else {
linkBefore(element,node(index));
}
return true;
}
//根據(jù)下標獲取元素
public int get(int index){
checkElementIndex(index);
return node(index).data;
}
//獲取第一個元素
public Integer getFirst(){
Node f=head;
if (f==null){
throw new NoSuchElementException();
} else {
return f.data;
}
}
//獲取最后一個元素
public Integer getLast(){
if (size==0){
throw new NoSuchElementException();
}
int index=size-1;
return node(index).data;
}
//刪除第一個元素
public Integer removeFirst(){
Node f=head;
if (f==null){
throw new NoSuchElementException();
} else {
return unlink(head);
}
}
//刪除最后一個元素
public Integer removeLast(){
if (size==0){
throw new NoSuchElementException();
}
int index=size-1;
return unlink(node(index));
}
//根據(jù)索引刪除元素
public Integer remove(int index){
checkElementIndex(index);
return unlink(node(index));
}
//銷毀鏈表
public void destroyList(){
clearList();
}
//將鏈表置為空表
public void clearList() {
for (Node p=head;p!=null;){
Node next=p.next;//記錄下一個結點
p=null;//刪除當前結點
p=next;//指向下一個結點
}
size=0;
head=null;
}
//遍歷鏈表
public void traverseList(){
for (Node p=head;p!=null;){
System.out.println(p.data);
p=p.next;
}
}
//返回鏈表元素個數(shù)
public int size(){
return size;
}
//尾部添加結點
private void linkLast(int element){
Node cur =null,p;
if (size==0){//沒有結點時
head=new Node(element,null);
size++;
return;
}
for (p=head;p!=null;){//有結點時候
cur=p;
p=cur.next;
}
cur.next= new Node(element,null);//尾部添加元素
size++;
}
//在某結點之前插入結點
private void linkBefore(int element,Node node){
if (node==null){
linkLast(element);
} else {
Node p=head,q=p.next;
if (node.data==p.data){//node為結點時候
head= new Node(element, p);//在頭部插入元素
size++;
} else {
while (p!=null){
if (q.data==node.data) {
p.next= new Node(element,q);//在q之前(p之后)插入一個元素
size++;
break;
}
p=p.next;
q=p.next;
}
}
}
}
//刪除結點
private Integer unlink(Node node){
Integer deleteNodeData=null;
Node p=null;
deleteNodeData=node.data;
if (node.data==head.data){//該節(jié)點為頭結點
p=head;
head=p.next;
p=null;
size--;
} else {
Node q=head;
for (p=q.next;p!=null;){//使用兩個指針,p,q
if (p.data==node.data){
break;
}
q=q.next;//p始終為q的next結點
p=q.next;
}
q.next=p.next;
p=null;//刪除p
size--;
}
return deleteNodeData;
}
//數(shù)組下標是否越界
private Boolean isElementIndex(int index){
return index>=0&&index<size;
}
//插入位置是否越界
public Boolean isPositionIndex(int index){
return index>=0&&index<=size;
}
//檢驗下標是否越界，拋出異常
private void checkElementIndex(int index){
if(!isElementIndex(index)){
try {
throw new IndexOutOfBoundsException("下標越界");
} catch (Exception e) {
e.printStackTrace();
}
}
}
//檢驗插入下標是否越界，拋出異常
private void checkPositionIndex(int index){
if(!isPositionIndex(index)){
try {
throw new IndexOutOfBoundsException("下標越界");
} catch (Exception e) {
e.printStackTrace();
}
}
}
//返回指定位置的元素
private Node node(int index){
int nowIndex = 0;
if(size>0){
for (Node p=head;p!=null;){
if (nowIndex==index){
return p;
}
p=p.next;
nowIndex++;
}
}
return null;
}
public static void main(String[] args) {
java.util.LinkedList linkedList0=new java.util.LinkedList();
linkedList0.add(6);
linkedList0.remove(0);
linkedList0.size();
linkedList0.peek();
//linkedList0.getFirst();
linkedList0.clear();
//測試
LinkedList linkedList=new LinkedList();
linkedList.add(2);
linkedList.add(6);
linkedList.add(0);
linkedList.add(3);
linkedList.add(8);
linkedList.add(10);
System.out.println(linkedList.get(0));
System.out.println(linkedList.getFirst());
System.out.println(linkedList.getLast());
System.out.println(linkedList.get(5));
System.out.println(linkedList.remove(5));
System.out.println(linkedList.remove(4));
linkedList.remove(2);
linkedList.remove(0);
linkedList.remove(0);
linkedList.remove(0);
linkedList.add(2);
linkedList.add(6);
linkedList.add(0);
linkedList.add(3);
linkedList.add(8);
linkedList.add(10);
linkedList.removeFirst();
linkedList.removeFirst();
linkedList.removeLast();
System.out.println(linkedList.size());
System.out.println("遍歷鏈表");
linkedList.traverseList();
linkedList.add(0,4);
linkedList.add(0,5);
linkedList.add(2,5);
linkedList.add(4,5);
linkedList.add(6,9);
linkedList.add(8,11);
linkedList.add(9,222);
// linkedList.linkBefore(3,new Node(3,null));
// linkedList.linkBefore(3,new Node(2,null));
// linkedList.linkBefore(3,new Node(2,null));
// linkedList.linkBefore(7,new Node(2,null));
// linkedList.linkBefore(9,new Node(7,null));
// linkedList.linkBefore(9,new Node(8,null));
System.out.println("遍歷鏈表");
linkedList.traverseList();
linkedList.clearList();
}
}
以上就是Java簡單實現(xiàn)線性表的鏈式存儲，更多功能可參考Java集合中的LinkedList實現(xiàn)。
相關文章
本文主要介紹了 Mybatis聯(lián)合查詢的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了Java在Word中添加多行圖片，圖文講解的很清晰，有對于這方面不懂得同學可以跟著研究下2021-02-02
跨域問題更是老生常談,隨便用標題去google或百度一下,能搜出一大片解決方案,這篇文章主要給大家介紹了關于SpringBoot中到底該如何解決跨域問題的相關資料,需要的朋友可以參考下2022-02-02
Spring Boot 簡化了 Spring 框架的使用,通過創(chuàng)建 `SpringApplication` 對象,判斷應用類型并設置初始化器和監(jiān)聽器,在 `run` 方法中,讀取配置并加載到 `Environment` 中,通過 Spring 事件機制和 `EnvironmentPostProcessor` 處理配置2025-02-02
springboot基于Mybatis mysql實現(xiàn)讀寫分離
這篇文章主要介紹了springboot基于Mybatis mysql實現(xiàn)讀寫分離,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了詳解springboot讀取yml配置的幾種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-10-10
MyBatis學習教程(五)-實現(xiàn)關聯(lián)表查詢方法詳解
本文給大家介紹mybatis關聯(lián)查詢，包括一對一關聯(lián)查詢，一對多關聯(lián)查詢，代碼簡單易懂，感興趣的朋友一起學習吧2016-05-05
很多時候我們需要根據(jù)不同的條件在容器中加載不同的Bean，或者根據(jù)不同的條件來選擇是否在容器中加載某個Bean，這就是Bean的加載控制，一般我們可以通過編程式或注解式兩種不同的方式來完成Bean的加載控制2022-12-12
MyBatis處理CLOB/BLOB類型數(shù)據(jù)以及解決讀取問題
這篇文章主要介紹了MyBatis處理CLOB/BLOB類型數(shù)據(jù)以及解決讀取問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
這篇文章主要介紹了springboot中@RequestMapping的用法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02