JAVA实现一个线程安全的循环单链表-pudn.com
有时候会有需要这样的场景，需要一个循环的链表做一些重复性的工作，比方说我们设计定时任务的时候，按照每一秒前进一个进行定时任务的读取，那么就需要有一个循环链表来做这样的数据结构，而java没有提供这样的一个数据结构，我在项目开发的时候也遇到了这样的问题，我们需要有管理定时任务，使用一个触发器来触发这些任务。
接口定义
package com.lee.berries.common.list;
/**
* 循环链表接口定义
* @author Liuxianwei
*
*/
public interface CircularLinkedList<E> {
/\*\*
\* 向链表插入一个元素，默认在尾部
\* @param item
*/
void add(E item);
/\*\*
\* 在链表的指定位置插入一个元素
\* @param index
\* @param item
*/
void add(int index, E item);
/\*\*
\* 向链表插入一个元素，默认在尾部
\* @param item
*/
void addLast(E item);
/\*\*
\* 向链表头部插入一个元素
\* @param item
*/
void addFirst(E item);
/\*\*
\* 删除链表指针的当前位置的元素
\* @return
*/
E remove();
/\*\*
\* 删除链表中的item元素
\* @param item
*/
void remove(E item);
/\*\*
\* 删除链表中index位置的元素
\* @param index
\* @return
*/
E remove(int index);
/\*\*
\* 删除链表头部元素
\* @return
*/
E removeFirst();
/\*\*
\* 删除链表尾部元素
\* @return
*/
E removeLast();
/\*\*
\* 移动链表当前位置指针到下一个位置
*/
void next();
/\*\*
\* 返回链表的当前位置
\* @return
*/
int currentIndex();
/\*\*
\* 返回链表当前位置元素
\* @return
*/
E current();
/\*\*
\* 返回链表的头部元素
\* @return
*/
E first();
/\*\*
\* 返回链表的尾部元素
\* @return
*/
E last();
/\*\*
\* 获取链表index位置的元素
\* @param index
\* @return
*/
E get(int index);
/\*\*
\* 清空链表
*/
void clear();
/\*\*
\* 返回链表的长度
\* @return
*/
int size();
/\*\*
\* 当前指针是否在头部
\* @return
*/
boolean isFirst();
/\*\*
\* 当前指针是否在尾部
\* @return
*/
boolean isLast();
/\*\*
\* 判断链表是否为空
\* @return
*/
boolean isEmpty();}
接下来就是实现类，我做了一个线程安全的实现。因为需要在多线程环境使用。这里使用了重入锁来保证线程安全
package com.lee.berries.common.list;
import java.util.Collection;
import java.util.concurrent.locks.ReentrantLock;
/**
* 实现一个线程安全的循环链表
* @author Liuxianwei
*
* @param <E>
*/
public class ConcurrentCircularLinkedList<E> implements CircularLinkedList<E> {
static class Node<E>{
E item;
Node<E> next;
Node(E item){
this.item = item;
}
}
final ReentrantLock lock = new ReentrantLock();
private Node<E> first;
private Node<E> last;
private Node<E> current;
private int currentIndex;
private int count = 0;
private int capacity;
public ConcurrentCircularLinkedList(){
this(Integer.MAX_VALUE);
}
public ConcurrentCircularLinkedList(int capacity){
this.capacity = capacity;
current = first = last = new Node<E>(null);
currentIndex = -1;
}
public ConcurrentCircularLinkedList(Collection<? extends E> c){
this(Integer.MAX_VALUE);
for(E item:c){
addLast(item);
}
}
@Override
public void add(E item) {
addLast(item);
}
@Override
public void add(int index, E item) {
lock.lock();
if(index < 0 || index > size()){
throw new ArrayIndexOutOfBoundsException();
}
if(count >= capacity){
throw new IllegalArgumentException();
}
try{
Node<E> node = new Node<E>(item);
/\*\*
\* 链表为null时,first,last,current都指向第一个元素
*/
if(this.isEmpty()){
first = node;
last = node;
current = first;
last.next = first;
currentIndex = 0;
}
else{
/\*\*
\* 头部插入的时候
*/
if(index == 0){
node.next = first;
first = node;
last.next = node;
}
/\*\*
\* 尾部插入
*/
else if(index == size()){
last.next = node;
node.next = first;
last = node;
}
else{
Node<E> n = this.first;
for(int i = 0; i < index; i++){
n = n.next;
}
node.next = n.next;
n.next = node;
}
if(index <= this.currentIndex){
this.currentIndex ++;
}
}
count++;
}
finally{
lock.unlock();
}
}
@Override
public void addLast(E item) {
if(count == 0){
add(0, item);
}
else{
add(count, item);
}
}
@Override
public void addFirst(E item) {
add(0, item);
}
private Node<E> getNode(int index){
if(index < 0 || index > size()){
throw new ArrayIndexOutOfBoundsException();
}
Node<E> node = first;
for(int i = 0; i < index; i++){
node = node.next;
}
return node;
}
@Override
public E remove() {
return remove(currentIndex);
}
@Override
public void remove(E item) {
lock.lock();
try{
Node<E> n = this.first;
for(int i = 0; i < size(); i++){
if(n.item.equals(item)){
remove(i);
break;
}
}
}
finally{
lock.unlock();
}
}
@Override
public E remove(int index) {
E item = null;
lock.lock();
try{
if(index < 0 || index > size()){
throw new ArrayIndexOutOfBoundsException();
}
if(count == 0){
throw new IllegalArgumentException();
}
/\*\*
\* 链表里面只剩下一个元素了
*/
if(first.next == first){
current = first = last = new Node<E>(null);
currentIndex = -1;
}
else{
/\*\*
\* 删除头部
*/
if(index == 0){
item = first.item;
if(current == first){
current = first.next;
}
Node<E> node = first;
first = first.next;
last.next = first;
node.next = null;
}
/\*\*
\* 删除尾部
*/
else if(index == (size() - 1)){
item = last.item;
Node<E> pre = getNode(index - 1);
if(current == last){
current = pre;
currentIndex--;
}
pre.next = first;
last.next = null;
last = pre;
}
else{
Node<E> pre = getNode(index - 1);
Node<E> node = pre.next;
item = node.item;
if(node == current){
current = node.next;
}
pre.next = node.next;
node.next = null;
if(index < currentIndex){
currentIndex --;
}
}
}
count --;
}
finally{
lock.unlock();
}
return item;
}
@Override
public E removeFirst() {
return remove(0);
}
@Override
public E removeLast() {
return remove(size()-1);
}
@Override
public void next() {
lock.lock();
try{
current = current.next;
currentIndex++;
if(current == first){
currentIndex = 0;
}
}
finally{
lock.unlock();
}
}
@Override
public int currentIndex() {
return this.currentIndex;
}
@Override
public E current() {
return get(currentIndex);
}
@Override
public E first() {
return first.item;
}
@Override
public E last() {
return last.item;
}
@Override
public E get(int index){
return null;
}
@Override
public void clear() {
}
@Override
public int size() {
return count;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public boolean isFirst() {
return this.currentIndex == 0;
}
@Override
public boolean isLast() {
return this.currentIndex == (size() - 1);
}
@Override
public String toString() {
if(isEmpty()){
return "\[\]";
}
StringBuffer buffer = new StringBuffer();
buffer.append("\[");
Node<E> node = first;
while(true){
buffer.append(node.item);
buffer.append(", ");
node = node.next;
if(node.next == first){
if(node != first){
buffer.append(node.item);
}
break;
}
}
buffer.append("\]");
return buffer.toString();
}
}
然后做一个简单的算法例子来验证功能的可用性，
100个人围成圆圈，从1开始报数，喊道3人的时候退出，重复。直到剩下最后一个人。
import org.junit.Test;
import com.lee.berries.common.list.CircularLinkedList;
import com.lee.berries.common.list.ConcurrentCircularLinkedList;
public class CircularLinkedListTest {
@Test
public void Test(){
CircularLinkedList<String> list = new ConcurrentCircularLinkedList<String>();
for(int i = 1; i < 101; i++){
list.add("" + i);
}
int count = 1;
while(list.size() > 1){
list.next();
count++;
if(count % 3 == 0){
System.out.println(list.remove() + "退出！");
count++;
}
}
System.out.println(list.toString());
}}
代码见附件 或者去我的github下载https://git.oschina.net/liuxianwei/berries/tree/master/berries-common/src/main/java/com/lee/berries/common/list
原网址: 访问
创建于: 2022-10-31 00:21:33
目录: default
标签: 无
未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到
最新评论