JAVA实现一个线程安全的循环单链表

有时候会有需要这样的场景，需要一个循环的链表做一些重复性的工作，比方说我们设计定时任务的时候，按照每一秒前进一个进行定时任务的读取，那么就需要有一个循环链表来做这样的数据结构，而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