【学点数据结构和算法】02-链表

/**
 * @Author: Alice菌
 * @Date: 2020/6/7 20:35
 * @Description:
 */
public class OwnLinkedList {

    // 头结点指针
    private Node head;

    // 尾节点指针
    private Node last;

    // 链表实际长度
    private int size;



    public void insert(int index,int data) throws Exception{

        if (index <0 || index > size){
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }

        Node insertedNode = new Node(data);

        if (size == 0){
           // 空链表
           head = insertedNode;
           last = insertedNode;
        }else if (index == 0){
            // 在头部插入
            insertedNode.next = head;
            head = insertedNode;
        }else if (size == index){
            // 插入尾部
            last.next = insertedNode;
            last = insertedNode;
        }else {
            // 在中间插入
            // 获取该位置的原节点
            Node preNode = get(index - 1);
            // 新插入节点接替原节点的指针指向位置
            insertedNode.next = preNode.next;
            // 原节点的指针指向新节点
            preNode.next = insertedNode;
        }

        // 链表的长度+1
        size++;
    }

    public Node remove(int index) throws Exception{

        if (index <0 || index >= size){
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }
        // 创建一个节点对象,保存需要删除的节点
        Node removedNode = null;

        if(index == 0){
            //删除头节点
            removedNode = head;
            //原头节点的位置后移
            head = head.next;
        }else if (index == size-1){
            // 删除尾节点
            // 获取到尾节点的前一个元素prevNode
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            // 将prevNode的指针指向null[间接删除了尾节点]
            prevNode.next = null;
            // 现在尾节点变成了prevNode
            last = prevNode;
        }else {
            // 删除的是中间节点
            // 获取到需要删除节点的前一个节点preNode
            Node preNode = get(index - 1);
            // 获取到需要删除节点的后一个节点nextNode
            Node nextNode = preNode.next.next;
            removedNode = preNode.next;
            // 将preNode的指针指向nextNode[间接删除了中间节点]
            preNode.next = nextNode;
        }
        // 链表的长度-1
        size--;
        // 返回被删除的节点
        return removedNode;
    }

    /**
     * 链表查找元素
     * @param index 查找的位置
     * @return 返回获取到的Node节点元素
     * @throws Exception 抛出异常
     */
    public Node get(int index) throws Exception{
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("超出链表节点范围!");
        }

        // 获取到头结点
        Node temp = head;
        // 通过遍历，依次获取到每个节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }


    public void output(){

        Node temp = head;

        while (temp!=null) {

            // 打印节点的内容data
            System.out.println(temp.data);
            // 不断通过一个节点的next指针，找到下一个节点
            temp = temp.next;
        }
    }


    /**
     * 链表节点
     */
    private static class Node{

        // 当前的数据
        int data;

        // 指针，指向下一个节点
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) throws Exception {

        // 新建一个链表对象
        OwnLinkedList ownLinkedList = new OwnLinkedList();

        // 添加元素
        ownLinkedList.insert(0,3);
        ownLinkedList.insert(0,4);
        ownLinkedList.insert(2,9);
        ownLinkedList.insert(3,5);
        ownLinkedList.insert(1,6);
        // 删除头节点
        ownLinkedList.remove(0);
        // 打印链表内容
        ownLinkedList.output();

        //6
        //3
        //9
        //5
    }

}