链表:循环链表

接口类:

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());

    }
}
image.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。