手写封装双向循环链表

/ 默认分类 / 0 条评论 / 1014浏览

1.节点实现

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

import cn.zh54.Node;
import cn.zh54.双向链表.BothWayNode;

import java.util.Optional;

/**
 * @author zuohui
 * @date 2020/3/4 - 17:02
 */
public class BothWayLoopNode implements Node {

    BothWayLoopNode pre;

    BothWayLoopNode next;

    Integer data;

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

    public BothWayLoopNode() {

    }

    @Override
    public String toString() {
        return Optional.ofNullable(pre).orElse(new BothWayLoopNode()).data + " <= " + data + " => " + Optional.ofNullable(next).orElse(new BothWayLoopNode()).data;
    }

}

2.链表实现

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

import cn.zh54.LinkedList;
import cn.zh54.Node;

import java.util.SimpleTimeZone;

/**
 * @author zuohui
 * @date 2020/3/4 - 17:02
 */
public class BothWayLoopLinkedList implements LinkedList {

    BothWayLoopNode head;

    BothWayLoopNode tail;

    int size;

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

    }

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

        Node node = getNode(index);
        BothWayLoopNode nodeAdd = ((BothWayLoopNode) node);
        nodeAdd.pre.next = newNode;
        newNode.next = nodeAdd;
        newNode.pre = nodeAdd.pre;
        nodeAdd.pre = newNode;
        size++;
    }

    @Override
    public void remove() {
        if(size == 0){
            throwOutOfRangeException();
        }
        head.pre = tail.pre;
        tail.pre.next = head;
        tail = tail.pre;
        size--;
    }

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

        if(index == 0){
            tail.next = head.next;
            head.next.pre = tail;
            head = head.next;
            size--;
            return;
        }
        Node node = getNode(index);
        BothWayLoopNode nodeRemove = (BothWayLoopNode) node;
        nodeRemove.pre.next = nodeRemove.next;
        nodeRemove.next.pre = nodeRemove.pre;
        size--;
    }

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

    @Override
    public Integer get(Integer index) {
        return null;
    }

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

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

        int times = 0;
        BothWayLoopNode currentNode = head.next;
        while (currentNode.next != head){
            if(++times == index){
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }

    @Override
    public void print() {
        if(size == 0){
            System.out.println("空链表");
            return;
        }
        BothWayLoopNode currentNode = head;
        System.out.println(currentNode);
        while (currentNode.next != head){
            System.out.println(currentNode.next);
            currentNode = currentNode.next;
        }
    }

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

  1. 简单测试
    public static void main(String[] args) {
        BothWayLoopLinkedList list = new BothWayLoopLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(2,12121);
        list.add(6);
        list.remove(3);
        list.print();
    }
    
-----
6 <= 1 => 2
1 <= 2 => 12121
2 <= 12121 => 4
12121 <= 4 => 5
4 <= 5 => 6
5 <= 6 => 1