Java 单链表数据结构的增删改查教程

我就废话不多说了，大家还是直接看代码吧~

package 链表;

/**
 *
 *1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 **/
public class SinglyLinkedList {
  private Node head = null;
  //查找操作
  public Node findByValue(int value){
    Node p = head; //从链表头部开始查找
    while(p.next != null && p.data != value){//如果数据不相等并且下一个节点不为null,继续查找
      p = p.next;
    }
    return p;
  }
  //通过index查找
  public Node findByIndex(int index){
    Node p = head; //从链表头部开始查找
    int count = 0; //指针计数器
    while(p.next != null && index != count){ //当下个节点不为null,并且计数器不等于index的时候继续查找
      p = p.next;
      count++;
    }
    return p;
  }
  //无头部节点(哨兵),表头部插入一个值,这种操作和输入的顺序相反,逆序
  public void insertToHead(int value){
    Node newNode = new Node(value,null);
    insertToHead(newNode);
  }
 //无头部节点(哨兵),表头部插入新节点,这种操作和输入的顺序相反,逆序
  public void insertToHead(Node newNode){
    if(head == null){
      head = newNode;
    }else{
      newNode.next = head;
      head = newNode;
    }
  }

  //链表尾部插入,按顺序插入,时间复杂度平均为O(n),这个可以优化,定义多一个尾部节点,不存储任何数据,时间复杂度未O(1)
  public void insertTail(int value){
    Node newNode = new Node(value,null);
    if(head == null){//链表为空
      head = newNode;
    }else{//直接从链表头开始找,知道找到链尾节点
      Node curr = head;
      while(curr.next != null){
        curr = curr.next;
      }
      curr.next = newNode;
    }
  }
  //在指定节点后面插入新节点,直接在这个节点后面断开连接,直接插入
  public void insertAfter(Node p,int value){
    Node newNode = new Node(value,null);
    insertAfter(p,newNode);
  }

  //在指定节点后面插入新节点,直接在这个节点后面断开连接,直接插入
  public void insertAfter(Node p,Node newNode){
    if(p == null){
      return;
    }
    newNode.next = p.next;
    p.next = newNode;
  }
  //在指定节点前面插入新节点
  public void insertBefore(Node p,int value){
    Node newNode = new Node(value,null);
    insertBefore(p,newNode);
  }
  //在指定节点前面插入新节点
  public void insertBefore(Node p,Node newNode){
    if(p == null){
      return;
    }
    if(p == head){//如果指定节点是头节点
      insertToHead(p);
      return;
    }
    Node curr = head;//当前节点,(查找指定节点p的前一个节点,当curr的下个节点等于指定节点时候,curr就是指定节点的前一个节点
    while(curr != null && curr.next != p){//当前节点不为null,当前节点的下个节点不等于指点节点,则继续查找
      curr = curr.next;
    }
    if(curr == null){//未找到指定节点p
      return;
    }
    newNode.next = p;
    curr.next = newNode;
  }
  //删除指定节点
  public void deleteByNode(Node p){
    if(p == null || p == head){
      return;
    }
    Node curr = head;//从链头开始查找,curr是当前节点,查找指定节点p的前一个节点,当curr的下个节点等于指定节点时候,curr就是指定节点的前一个节点
    while(curr != null && curr.next != p){//当前节点不为null并且,下个节点不等于指定节点时候继续查找
      curr = curr.next;
    }
    if(curr == null){//未找到指定节点
      return;
    }
    curr.next = curr.next.next;
  }
  //删除指定值
  public void deleteByValue(int value){
    if(head == null){
      return;
    }
    Node curr = head;//当前节点,从链表头开始查找
    Node pre = null;//当前节点的前一个节点,找查找指定的过程,要不断地保存当前节点的前一个节点
    while(curr != null && curr.data != value){
      pre = curr;
      curr = curr.next;
    }
    if(curr == null){//未找到指定的值
      return ;
    }
    if(pre == null){//链表头数据就是指定的值
      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;
    }
  } 

  //单链表数据结构类,以存储int类型数据为例
  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数据库的常规操作进行了简单的封装。

get,find方法分别对应了单行数据查询和list查询。

这些查询都要开启和关闭Hbase数据库链接

@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); 获取数据库链接
releaseTable(tableName, table); 释放链接

在HbaseUtils.getHTable：

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

看见这个大家应该都有是曾相似的感觉吧，这和Spring事务管理核心类TransactionSynchronizationManager很像，而实现也基本一样

都是通过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方法执行前去获取Hbase链接并通过HbaseSynchronizationManager.bindResource(tableName, table);绑定到线程中。

finally中releaseTable。

Aop配置如下：

<!-- 自动扫描beans+注解功能注册 -->
 <context:component-scan base-package="com.xxx.xxx" />

 <!-- 根据配置文件生成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数据库链接的开启和关闭 -->
 <aop:config>
 <aop:pointcut id="allManagerMethod"
  expression="execution(* com.xxx.xxx.*.service..*(..))" />
 <aop:advisor advice-ref="hbaseInterceptor" pointcut-ref="allManagerMethod" />
 </aop:config>

Hbase的数据库表链接跟传统数据库不太一样， 开启链接必需要表名， 所以HbaseInterceptor中必需设置private String[] tableNames;

在进入servcie方法时，tableNames中对应的表链接都会开启。这必然会造成浪费，因为并不是每个service都会把表都查询一遍。

以上这篇Java 单链表数据结构的增删改查教程就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。