<<漫画算法>>--数据结构之链表

大部分记录均来自小灰漫画算法

• 什么是链表？
  物理上非连续、非顺序的数据结构。由若干节点组成。

  
  链表.png
• 链表的基本操作
  ①查找节点：只能从头节点开始向后一个节点逐一查找。
  第一步：将查找的指针定位到头节点；
  第二步：根据头节点的next指针，定位到第二个节点；
  第三布：根据第二个节点的next指针，定位到第三个节点。依次类推。
  ②更新节点：不考虑查找的情况下，直接旧数据替换成新数据即可。
  ③插入节点：
• 头部插入
  第一步：新节点的Next指针指向原先的头节点
  第二步：新节点变为链表的头节点
• 尾部插入
  最后一个节点的next指向新插入节点即可
• 中间插入
  第一步：新节点的Next指针，指向插入位置的节点；
  第二部：插入位置的前置节点next指针，指向新节点。
  ④删除节点：
• 头部删除
  链表头节点设置为原先头节点的next指针
• 尾部删除
  指向最后一个元素的Next指针，置为Null即可
• 中间删除
  删除节点的前置节点的Next指针，指向要删除元素的下一个节点即可。

    //记录链表的长度
    private int size = 0;
    //头尾指针
    private Node head;
    private Node last;

    /**
     * 插入元素
     * @param data：插入元素
     * @param index：插入位置(从0开始)
     */
    public void insert(int data,int index){
        //TODO:判断插入位置
        if(index < 0 && index > size) {
            throw new IndexOutOfBoundsException("超出链表范围");
        }
        //TODO:创建要插入的元素
        Node node = new Node(data);
        //TODO:插入位置判断(头部，尾部，中间)
        if(size == 0) {//创建一个链表
            head = last = node;
        }else if(index == 0) {
            node.next = head;
            head = node;
        }else if(index == size) {
            last.next = node;
            last  = node;
        }else{
            Node preNode = findNode(index - 1);
            node.next = preNode.next;
            preNode.next = node;
        }
        //TODO:插入后链表长度加1
        size++;
    }

    /**
     * 根据位置查找对应的节点
     * @param index：查找的位置
     * @return：查询结果
     */
    public Node findNode(int index){
        //TODO:判断查询位置是否合法
        if(index < 0 && index > size) {
            throw new IndexOutOfBoundsException("超出链表查询范围");
        }
        //TODO:头节点开始逐一向后一节点查找
        if(size == 0) {
            throw new IndexOutOfBoundsException("暂无链表");
        }else{
            Node node = head;
            for (int pos = 0 ; pos < index ; pos++){
                node = node.next;
            }
            return node;
        }
    }

    /**
     * 根据位置跟新节点
     * @param index
     * @param node
     */
    public void updateNode(int index,Node node){
        //TODO:判断查询位置是否合法
        if(index < 0 && index > size) {
            throw new IndexOutOfBoundsException("超出链表查询范围");
        }
        if(size == 0) {
            throw new IndexOutOfBoundsException("暂无链表");
        }else{
            Node findNode = findNode(index);
            findNode.data = node.data;
        }
    }

    /**
     * 刪除元素
     * @param index
     */
    public void deleteNode(int index){
        //TODO:判断查询位置是否合法
        if(index < 0 && index > size) {
            throw new IndexOutOfBoundsException("超出链表查询范围");
        }
        if(size == 0) {
            throw new IndexOutOfBoundsException("暂无链表");
        }else{
            Node node = findNode(index);
            if(index == 0) {
                head = node.next;
            }else if(index == size - 1) {
                node.next = null;
            }else{
                Node preNode = findNode(index - 1);
                preNode.next = node.next;
            }
            //TODO:插入后链表长度减1
            size--;
        }
    }

    //包含元素跟指针
    private static class Node{
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    public void output(){
        Node node = head;
        if(node != null) {
            for (int i = 0 ; i < size ; i++){
                System.out.println("Node : " + node.data);
                node = node.next;
            }
        }
    }

    public static void main(String [] args){
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(3,0);
        myLinkedList.insert(5,1);
        myLinkedList.insert(7,2);
        myLinkedList.insert(9,3);
        myLinkedList.insert(1,1);
        myLinkedList.output();
        myLinkedList.deleteNode(0);
        myLinkedList.deleteNode(2);
        myLinkedList.output();
    }

总结；链表再删除和插入方面效率远高于更新跟查找