Java 單鏈表數(shù)據(jù)結構的增刪改查教程
更新時間：2020年10月21日 09:50:23 作者：qq_28394359
這篇文章主要介紹了Java 單鏈表數(shù)據(jù)結構的增刪改查教程，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
我就廢話不多說了，大家還是直接看代碼吧~
package 鏈表;
/**
*
*1）單鏈表的插入、刪除、查找操作；
* 2）鏈表中存儲的是int類型的數(shù)據(jù)；
**/
public class SinglyLinkedList {
private Node head = null;
//查找操作
public Node findByValue(int value){
Node p = head; //從鏈表頭部開始查找
while(p.next != null && p.data != value){//如果數(shù)據(jù)不相等并且下一個節(jié)點不為null,繼續(xù)查找
p = p.next;
}
return p;
}
//通過index查找
public Node findByIndex(int index){
Node p = head; //從鏈表頭部開始查找
int count = 0; //指針計數(shù)器
while(p.next != null && index != count){ //當下個節(jié)點不為null,并且計數(shù)器不等于index的時候繼續(xù)查找
p = p.next;
count++;
}
return p;
}
//無頭部節(jié)點(哨兵),表頭部插入一個值,這種操作和輸入的順序相反,逆序
public void insertToHead(int value){
Node newNode = new Node(value,null);
insertToHead(newNode);
}
//無頭部節(jié)點(哨兵),表頭部插入新節(jié)點,這種操作和輸入的順序相反,逆序
public void insertToHead(Node newNode){
if(head == null){
head = newNode;
}else{
newNode.next = head;
head = newNode;
}
}
//鏈表尾部插入,按順序插入,時間復雜度平均為O(n),這個可以優(yōu)化,定義多一個尾部節(jié)點,不存儲任何數(shù)據(jù),時間復雜度未O(1)
public void insertTail(int value){
Node newNode = new Node(value,null);
if(head == null){//鏈表為空
head = newNode;
}else{//直接從鏈表頭開始找,知道找到鏈尾節(jié)點
Node curr = head;
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
}
//在指定節(jié)點后面插入新節(jié)點,直接在這個節(jié)點后面斷開連接,直接插入
public void insertAfter(Node p,int value){
Node newNode = new Node(value,null);
insertAfter(p,newNode);
}
//在指定節(jié)點后面插入新節(jié)點,直接在這個節(jié)點后面斷開連接,直接插入
public void insertAfter(Node p,Node newNode){
if(p == null){
return;
}
newNode.next = p.next;
p.next = newNode;
}
//在指定節(jié)點前面插入新節(jié)點
public void insertBefore(Node p,int value){
Node newNode = new Node(value,null);
insertBefore(p,newNode);
}
//在指定節(jié)點前面插入新節(jié)點
public void insertBefore(Node p,Node newNode){
if(p == null){
return;
}
if(p == head){//如果指定節(jié)點是頭節(jié)點
insertToHead(p);
return;
}
Node curr = head;//當前節(jié)點,(查找指定節(jié)點p的前一個節(jié)點,當curr的下個節(jié)點等于指定節(jié)點時候,curr就是指定節(jié)點的前一個節(jié)點
while(curr != null && curr.next != p){//當前節(jié)點不為null,當前節(jié)點的下個節(jié)點不等于指點節(jié)點,則繼續(xù)查找
curr = curr.next;
}
if(curr == null){//未找到指定節(jié)點p
return;
}
newNode.next = p;
curr.next = newNode;
}
//刪除指定節(jié)點
public void deleteByNode(Node p){
if(p == null || p == head){
return;
}
Node curr = head;//從鏈頭開始查找,curr是當前節(jié)點,查找指定節(jié)點p的前一個節(jié)點,當curr的下個節(jié)點等于指定節(jié)點時候,curr就是指定節(jié)點的前一個節(jié)點
while(curr != null && curr.next != p){//當前節(jié)點不為null并且,下個節(jié)點不等于指定節(jié)點時候繼續(xù)查找
curr = curr.next;
}
if(curr == null){//未找到指定節(jié)點
return;
}
curr.next = curr.next.next;
}
//刪除指定值
public void deleteByValue(int value){
if(head == null){
return;
}
Node curr = head;//當前節(jié)點,從鏈表頭開始查找
Node pre = null;//當前節(jié)點的前一個節(jié)點,找查找指定的過程,要不斷地保存當前節(jié)點的前一個節(jié)點
while(curr != null && curr.data != value){
pre = curr;
curr = curr.next;
}
if(curr == null){//未找到指定的值
return ;
}
if(pre == null){//鏈表頭數(shù)據(jù)就是指定的值
head = head.next;
}else{
pre.next = pre.next.next;//或者pre.next = curr.next;
}
}
//打印鏈表
public void printAll() {
Node curr = head;
while(curr != null){
System.out.println(curr.data);
curr = curr.next;
}
}
//單鏈表數(shù)據(jù)結構類,以存儲int類型數(shù)據(jù)為例
public class Node{
private int data;
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData(){
return data;
}
}
public static void main(String[]args) {
老師代碼.linkedlist06.SinglyLinkedList link = new 老師代碼.linkedlist06.SinglyLinkedList();
System.out.println("hello");
int data[] = {1, 2, 5, 3, 1};
for (int i = 0; i < data.length; i++) {
//link.insertToHead(data[i]);
link.insertTail(data[i]);
}
System.out.println("打印原始:");
link.printAll();
}
}
補充知識：Hbase+Spring Aop 配置Hbase鏈接的開啟和關閉
Spring 提供了HbaseTemplate 對Hbase數(shù)據(jù)庫的常規(guī)操作進行了簡單的封裝。
get,find方法分別對應了單行數(shù)據(jù)查詢和list查詢。
這些查詢都要開啟和關閉Hbase數(shù)據(jù)庫鏈接
@Override
public <T> T execute(String tableName, TableCallback<T> action) {
Assert.notNull(action, "Callback object must not be null");
Assert.notNull(tableName, "No table specified");
HTableInterface table = getTable(tableName);
try {
boolean previousFlushSetting = applyFlushSetting(table);
T result = action.doInTable(table);
flushIfNecessary(table, previousFlushSetting);
return result;
} catch (Throwable th) {
if (th instanceof Error) {
throw ((Error) th);
}
if (th instanceof RuntimeException) {
throw ((RuntimeException) th);
}
throw convertHbaseAccessException((Exception) th);
} finally {
releaseTable(tableName, table);
}
}
private HTableInterface getTable(String tableName) {
return HbaseUtils.getHTable(tableName, getConfiguration(), getCharset(), getTableFactory());
}
private void releaseTable(String tableName, HTableInterface table) {
HbaseUtils.releaseTable(tableName, table, getTableFactory());
}
HTableInterface table = getTable(tableName); 獲取數(shù)據(jù)庫鏈接
releaseTable(tableName, table); 釋放鏈接
在HbaseUtils.getHTable：
if (HbaseSynchronizationManager.hasResource(tableName)) {
return (HTable) HbaseSynchronizationManager.getResource(tableName);
}
看見這個大家應該都有是曾相似的感覺吧，這和Spring事務管理核心類TransactionSynchronizationManager很像，而實現(xiàn)也基本一樣
都是通過ThreadLocal將鏈接保存到當前線程中。
我們要做的就是要像Srping 事務配置一樣，在進入service方法時通過Aop機制將tableNames對應的鏈接加入到線程中。
Spring提供了這個Aop方法攔截器 HbaseInterceptor：
public Object invoke(MethodInvocation methodInvocation) throws Throwable {
Set<String> boundTables = new LinkedHashSet<String>();
for (String tableName : tableNames) {
if (!HbaseSynchronizationManager.hasResource(tableName)) {
boundTables.add(tableName);
HTableInterface table = HbaseUtils.getHTable(tableName, getConfiguration(), getCharset(), getTableFactory());
HbaseSynchronizationManager.bindResource(tableName, table);
}
}
try {
Object retVal = methodInvocation.proceed();
return retVal;
} catch (Exception ex) {
if (this.exceptionConversionEnabled) {
throw convertHBaseException(ex);
}
else {
throw ex;
}
} finally {
for (String tableName : boundTables) {
HTableInterface table = (HTableInterface) HbaseSynchronizationManager.unbindResourceIfPossible(tableName);
if (table != null) {
HbaseUtils.releaseTable(tableName, table);
}
else {
log.warn("Table [" + tableName + "] unbound from the thread by somebody else; cannot guarantee proper clean-up");
}
}
}
}
很明顯在
Object retVal = methodInvocation.proceed();
也就是我們的service方法執(zhí)行前去獲取Hbase鏈接并通過HbaseSynchronizationManager.bindResource(tableName, table);綁定到線程中。
finally中releaseTable。
Aop配置如下：
<!-- 自動掃描beans+注解功能注冊 --> <context:component-scan base-package="com.xxx.xxx" /> <!-- 根據(jù)配置文件生成hadoopConfiguration --> <hdp:configuration resources="classpath:/hbase-site.xml" /> <!-- hadoopConfiguration == hdp:configuration --> <!-- <hdp:hbase-configuration configuration-ref="hadoopConfiguration" /> --> <bean id="hbaseTemplate" class="org.springframework.data.hadoop.hbase.HbaseTemplate"> <!-- hadoopConfiguration == hdp:configuration --> <property name="configuration" ref="hadoopConfiguration" /> </bean> <bean id="hbaseInterceptor" class="org.springframework.data.hadoop.hbase.HbaseInterceptor"> <property name="configuration" ref="hadoopConfiguration" /> <property name="tableNames"> <list> <value>table_name1</value> <value>table_name2</value> </list> </property> </bean> <!-- 使用aop增強, 織入hbase數(shù)據(jù)庫鏈接的開啟和關閉 --> <aop:config> <aop:pointcut id="allManagerMethod" expression="execution(* com.xxx.xxx.*.service..*(..))" /> <aop:advisor advice-ref="hbaseInterceptor" pointcut-ref="allManagerMethod" /> </aop:config>
Hbase的數(shù)據(jù)庫表鏈接跟傳統(tǒng)數(shù)據(jù)庫不太一樣， 開啟鏈接必需要表名， 所以HbaseInterceptor中必需設置private String[] tableNames;
在進入servcie方法時，tableNames中對應的表鏈接都會開啟。這必然會造成浪費，因為并不是每個service都會把表都查詢一遍。
以上這篇Java 單鏈表數(shù)據(jù)結構的增刪改查教程就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
Java Optional解決空指針異常總結(java 8 功能)
這篇文章主要介紹了Java Optional解決空指針異?？偨Y(java 8 功能)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
下面小編就為大家?guī)硪黄獪\談cookie 和session 的區(qū)別。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
日常工作中?Map?絕對是我們?Java?程序員高頻使用的一種數(shù)據(jù)結構，那?Map?都有哪些遍歷方式呢？這篇文章就帶大家看一下，看看你經常使用的是哪一種2022-11-11
在開發(fā)中,日志記錄是保障應用程序健壯性、可維護性的重要手段,通過日志,我們可以記錄系統(tǒng)的運行狀態(tài)、捕獲異常并進行調試,Spring Boot 默認使用的是 Logback,但你也可以根據(jù)需求選擇其他框架,以下是幾種常用的日志集成方法,需要的朋友可以參考下2024-10-10
這篇文章主要介紹了Java探索之string字符串的應用代碼示例，具有一定參考價值，需要的朋友可以了解下。2017-10-10
這篇文章主要為大家介紹了Spring JPA 錯題集解決案例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
上篇文章記錄自定義切面,下邊記錄使用注解來編寫自定義切面,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-06-06
本篇文章主要介紹了使用Spring自定義注解實現(xiàn)任務路由的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
這篇文章主要介紹了Java冒泡排序簡單實現(xiàn)，具有一定借鑒價值，需要的朋友可以參考下。2017-12-12
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡單了解下堆結構2022-01-01