手写封装单向循环链表

1. 节点实现

package cn.zh54.单向循环链表;

import cn.zh54.Node;

/**
 * @author zuohui
 * @date 2020/3/4 - 13:38
 */
public class SingleWayLoopNode implements Node {

    SingleWayLoopNode next;

    Integer data;

    public SingleWayLoopNode() {
    }

    public SingleWayLoopNode(Integer data,SingleWayLoopNode next) {
        this.next = next;
        this.data = data;
    }

    @Override
    public String toString() {
        return data + " => " + next.data;
    }

}

2.链表实现

package cn.zh54.单向循环链表;

import cn.zh54.LinkedList;
import cn.zh54.Node;
import cn.zh54.单向链表.SingleWayNode;

/**
 * @author zuohui
 * @date 2020/3/4 - 13:42
 */
public class SingleWayLoopLinkedList implements LinkedList {

    SingleWayLoopNode head;

    SingleWayLoopNode tail;

    int size;

    @Override
    public void add(Integer e) {
        SingleWayLoopNode newNode = new SingleWayLoopNode(e,null);
        if(size == 0){
            head = newNode;
            tail = newNode;
            head.next = tail;
            size++;
            return;
        }
        tail.next = newNode;
        newNode.next = head;
        tail = newNode;
        size++;
    }

    @Override
    public void add(Integer index, Integer e) {
        SingleWayLoopNode newNode = new SingleWayLoopNode(e,null);
        checkIndexLegal(index);
        if(index > size){
            throwOutOfRangeException();
        }

        if(index == 0){
            tail.next = newNode;
            newNode.next = head;
            head = newNode;
            size++;
            return;
        }

        if(index == size){
            add(e);
            return;
        }

        int times = 0;
        SingleWayLoopNode preNode = head;
        SingleWayLoopNode currentNode = head.next;
        while (currentNode.next != null){
            if((++times) == index){
                preNode.next = newNode;
                newNode.next = currentNode;
                size++;
                break;
            }
            preNode = currentNode;
            currentNode = currentNode.next;
        }
    }

    @Override
    public void remove() {
        if(size == 0){
            throwOutOfRangeException();
        }
        if(size == 1){
            head = null;
            tail = null;
        }else{
            SingleWayLoopNode preNode = head;
            SingleWayLoopNode currentNode = head.next;
            while (currentNode.next != head){
                preNode = currentNode;
                currentNode = currentNode.next;
            }
            preNode.next = null;
            tail = preNode;
        }
        size--;
    }

    @Override
    public void remove(Integer index) {
        checkIndexLegal(index);
        if(index > size - 1){
            throwOutOfRangeException();
        }
        //删除尾部
        if(index == size - 1){
            remove();
        }
        //删除头部
        else if(index == 0){
            tail.next = head.next;
            size--;
        }
        //删除中间
        else{
            int times = 0;
            SingleWayLoopNode preNode = head;
            SingleWayLoopNode currentNode = head.next;
            //currentNode.next != null 表示，只遍历中间部位的元素
            while (currentNode.next != head){
                //++times因为不需要获取head
                if(++times == index){
                    preNode.next = currentNode.next;
                    size--;
                    break;
                }
            }
        }
    }

    @Override
    public Integer get() {
        Node node = getNode();
        if(node == null){
            return null;
        }
        return ((SingleWayLoopNode)node).data;
    }

    @Override
    public Integer get(Integer index) {
        Node node = getNode(index);
        if(node == null){
            return null;
        }
        return ((SingleWayLoopNode)node).data;
    }

    @Override
    public Node getNode() {
        if(size == 0){
            throwOutOfRangeException();
        }
        return tail;
    }

    @Override
    public Node getNode(Integer index) {
        checkIndexLegal(index);
        if (index > size - 1){
            throwOutOfRangeException();
        }

        int times = 0;
        SingleWayLoopNode currentNode = head;
        while (currentNode != null){
            //times++,因为包含获取head
            if(times++ == index){
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
    @Override
    public void print() {
//        SingleWayLoopNode currentNode = tail;
//        do{
//            System.out.println(currentNode);
//            currentNode = currentNode.next;
//        }while (currentNode.next != head);

        SingleWayLoopNode currentNode = head;
        System.out.println(currentNode);
        while (currentNode.next != head){
            System.out.println(currentNode = currentNode.next);
        }
    }

    @Override
    public Integer size() {
        return null;
    }
}

3. 简单测试

    public static void main(String[] args) {
        SingleWayLoopLinkedList list = new SingleWayLoopLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(2,1212);
        list.print();
    }

------
1 => 2
2 => 1212
1212 => 3
3 => 4
4 => 5
5 => 1

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/05/05 23:32