接口类:
public interface CircularLinkedList<E> {
public int size();
public void add(int index, E e);
public void addFirst(E e);
public void addLast(E e);
public E remove(int index);
public E removeFirst();
public E removeLast();
public E get(int index);
public void set(int index, E e);
public boolean contains(E e);
public boolean isEmpty();
}
实现类:
public class CircularLinkedListImpl<E> implements CircularLinkedList<E> {
//结点类
class Node{
public E e;
public Node next;
public Node(E e , Node next){
this.next = next;
this.e = e;
}
public Node(){
this.next = null;
this.e = null;
}
public Node(E e) {
this(e, null);
}
}
private int size;//链表中的元素个数
private Node dummyHead;//虚拟头结点;
//初始化
public CircularLinkedListImpl(){
dummyHead = new Node();
dummyHead.next = dummyHead;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public void add(int index , E e) {
//边界处理
if (index < 0 || index > size )
throw new IllegalArgumentException("the index is illegal,add is fail");
Node pre = dummyHead;
for (int i = 0 ; i < index ;i++ ){
pre = pre.next;
}
Node node = new Node(e);
node.next = pre.next;
pre.next = node;
size++;
}
@Override
public void addFirst(E e) {
add(0,e);
}
@Override
public void addLast(E e) {
add(size,e);
}
@Override
public E remove(int index) {
if (index < 0 || index >= size )
throw new IllegalArgumentException("the index is illegal,remove is fail");
Node pre = dummyHead;
for (int i = 0 ; i < index ; i++ ){
pre = pre.next;
}
E re = pre.next.e;
pre.next = pre.next.next;
size --;
return re;
}
@Override
public E removeFirst() {
return remove(0);
}
@Override
public E removeLast() {
return remove(size-1);
}
@Override
public E get(int index) {
if (index < 0 || index >= size )
throw new IllegalArgumentException("the index is illegal,get is fail");
Node node = dummyHead.next;
for (int i = 0 ; i < index ; i++ ){
node = node.next;
}
return node.e;
}
@Override
public void set(int index, E e) {
if (index < 0 || index >= size )
throw new IllegalArgumentException("the index is illegal,get is fail");
Node node = dummyHead.next;
for (int i = 0 ; i < index ; i++ ){
node = node.next;
}
node.e = e;
}
@Override
public boolean contains(E e) {
Node node = dummyHead.next;
for (int i = 0 ; i < size-1; i++){
if (node.e == e)
return true;
node = node.next;
}
return false;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node node = dummyHead.next;
while (node != dummyHead){
res.append(node.e+"->");
node = node.next;
}
res.append(dummyHead.next.e);
return res.toString();
}
}
测试:
public class Main {
public static void main(String[] args) {
CircularLinkedList<Integer> list = new CircularLinkedListImpl<>();
System.out.println(list);
for (int i = 0 ; i < 10 ; i++){
list.add(i,i);
System.out.println(list);
}
list.removeFirst();
System.out.println(list);
list.removeLast();
System.out.println(list);
System.out.println(list.get(2));
System.out.println(list.isEmpty());
System.out.println(list.size());
}
}