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 class='org.springframework.data.hadoop.hbase.HbaseTemplate'> <!-- hadoopConfiguration == hdp:configuration --> <property name='configuration' ref='hadoopConfiguration' /> </bean> <bean 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 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 单链表数据结构的增删改查教程就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持好吧啦网。