快捷導(dǎo)航

Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程

更新時(shí)間：2020年10月21日 09:50:23 作者：qq_28394359

這篇文章主要介紹了Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

我就廢話不多說了，大家還是直接看代碼吧~

package 鏈表;
 
/**
 *
 *1）單鏈表的插入、刪除、查找操作；
 * 2）鏈表中存儲(chǔ)的是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ù)不相等并且下一個(gè)節(jié)點(diǎn)不為null,繼續(xù)查找
      p = p.next;
    }
    return p;
  }
  //通過index查找
  public Node findByIndex(int index){
    Node p = head; //從鏈表頭部開始查找
    int count = 0; //指針計(jì)數(shù)器
    while(p.next != null && index != count){ //當(dāng)下個(gè)節(jié)點(diǎn)不為null,并且計(jì)數(shù)器不等于index的時(shí)候繼續(xù)查找
      p = p.next;
      count++;
    }
    return p;
  }
  //無(wú)頭部節(jié)點(diǎn)(哨兵),表頭部插入一個(gè)值,這種操作和輸入的順序相反,逆序
  public void insertToHead(int value){
    Node newNode = new Node(value,null);
    insertToHead(newNode);
  }
 //無(wú)頭部節(jié)點(diǎn)(哨兵),表頭部插入新節(jié)點(diǎn),這種操作和輸入的順序相反,逆序
  public void insertToHead(Node newNode){
    if(head == null){
      head = newNode;
    }else{
      newNode.next = head;
      head = newNode;
    }
  }
 
  //鏈表尾部插入,按順序插入,時(shí)間復(fù)雜度平均為O(n),這個(gè)可以優(yōu)化,定義多一個(gè)尾部節(jié)點(diǎn),不存儲(chǔ)任何數(shù)據(jù),時(shí)間復(fù)雜度未O(1)
  public void insertTail(int value){
    Node newNode = new Node(value,null);
    if(head == null){//鏈表為空
      head = newNode;
    }else{//直接從鏈表頭開始找,知道找到鏈尾節(jié)點(diǎn)
      Node curr = head;
      while(curr.next != null){
        curr = curr.next;
      }
      curr.next = newNode;
    }
  }
  //在指定節(jié)點(diǎn)后面插入新節(jié)點(diǎn),直接在這個(gè)節(jié)點(diǎn)后面斷開連接,直接插入
  public void insertAfter(Node p,int value){
    Node newNode = new Node(value,null);
    insertAfter(p,newNode);
  }
 
  //在指定節(jié)點(diǎn)后面插入新節(jié)點(diǎn),直接在這個(gè)節(jié)點(diǎn)后面斷開連接,直接插入
  public void insertAfter(Node p,Node newNode){
    if(p == null){
      return;
    }
    newNode.next = p.next;
    p.next = newNode;
  }
  //在指定節(jié)點(diǎn)前面插入新節(jié)點(diǎn)
  public void insertBefore(Node p,int value){
    Node newNode = new Node(value,null);
    insertBefore(p,newNode);
  }
  //在指定節(jié)點(diǎn)前面插入新節(jié)點(diǎn)
  public void insertBefore(Node p,Node newNode){
    if(p == null){
      return;
    }
    if(p == head){//如果指定節(jié)點(diǎn)是頭節(jié)點(diǎn)
      insertToHead(p);
      return;
    }
    Node curr = head;//當(dāng)前節(jié)點(diǎn),(查找指定節(jié)點(diǎn)p的前一個(gè)節(jié)點(diǎn),當(dāng)curr的下個(gè)節(jié)點(diǎn)等于指定節(jié)點(diǎn)時(shí)候,curr就是指定節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    while(curr != null && curr.next != p){//當(dāng)前節(jié)點(diǎn)不為null,當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)不等于指點(diǎn)節(jié)點(diǎn),則繼續(xù)查找
      curr = curr.next;
    }
    if(curr == null){//未找到指定節(jié)點(diǎn)p
      return;
    }
    newNode.next = p;
    curr.next = newNode;
  }
  //刪除指定節(jié)點(diǎn)
  public void deleteByNode(Node p){
    if(p == null || p == head){
      return;
    }
    Node curr = head;//從鏈頭開始查找,curr是當(dāng)前節(jié)點(diǎn),查找指定節(jié)點(diǎn)p的前一個(gè)節(jié)點(diǎn),當(dāng)curr的下個(gè)節(jié)點(diǎn)等于指定節(jié)點(diǎn)時(shí)候,curr就是指定節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    while(curr != null && curr.next != p){//當(dāng)前節(jié)點(diǎn)不為null并且,下個(gè)節(jié)點(diǎn)不等于指定節(jié)點(diǎn)時(shí)候繼續(xù)查找
      curr = curr.next;
    }
    if(curr == null){//未找到指定節(jié)點(diǎn)
      return;
    }
    curr.next = curr.next.next;
  }
  //刪除指定值
  public void deleteByValue(int value){
    if(head == null){
      return;
    }
    Node curr = head;//當(dāng)前節(jié)點(diǎn),從鏈表頭開始查找
    Node pre = null;//當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn),找查找指定的過程,要不斷地保存當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    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ù)結(jié)構(gòu)類,以存儲(chǔ)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();
  }
}

補(bǔ)充知識(shí)：Hbase+Spring Aop 配置Hbase鏈接的開啟和關(guān)閉

Spring 提供了HbaseTemplate 對(duì)Hbase數(shù)據(jù)庫(kù)的常規(guī)操作進(jìn)行了簡(jiǎn)單的封裝。

get,find方法分別對(duì)應(yīng)了單行數(shù)據(jù)查詢和list查詢。

這些查詢都要開啟和關(guān)閉Hbase數(shù)據(jù)庫(kù)鏈接

@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ù)庫(kù)鏈接
releaseTable(tableName, table); 釋放鏈接

在HbaseUtils.getHTable：

if (HbaseSynchronizationManager.hasResource(tableName)) {
  return (HTable) HbaseSynchronizationManager.getResource(tableName);
 }

看見這個(gè)大家應(yīng)該都有是曾相似的感覺吧，這和Spring事務(wù)管理核心類TransactionSynchronizationManager很像，而實(shí)現(xiàn)也基本一樣

都是通過ThreadLocal將鏈接保存到當(dāng)前線程中。

我們要做的就是要像Srping 事務(wù)配置一樣，在進(jìn)入service方法時(shí)通過Aop機(jī)制將tableNames對(duì)應(yīng)的鏈接加入到線程中。

Spring提供了這個(gè)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配置如下：

<!-- 自動(dòng)掃描beans+注解功能注冊(cè) -->
 <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增強(qiáng), 織入hbase數(shù)據(jù)庫(kù)鏈接的開啟和關(guān)閉 -->
 <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ù)庫(kù)表鏈接跟傳統(tǒng)數(shù)據(jù)庫(kù)不太一樣，開啟鏈接必需要表名，所以HbaseInterceptor中必需設(shè)置private String[] tableNames;

在進(jìn)入servcie方法時(shí)，tableNames中對(duì)應(yīng)的表鏈接都會(huì)開啟。這必然會(huì)造成浪費(fèi)，因?yàn)椴⒉皇敲總€(gè)service都會(huì)把表都查詢一遍。

以上這篇Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: