【数据结构】- 链表

链表

链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。下面对单向链表做一个介绍。

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

image.png
image.png

单项列表Demo

public class MyLink {

    Node head = null;

    class Node {
        Node next;
        int data;

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

    public void addNode(int d) {
        Node node = new Node(d);
        if (head == null) {
            head = node;
            return;
        }
        Node tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = node;
    }

    public boolean deleteNode(int index) {
        if (index < 0 || index >= length()) {
            return false;
        }
        if (index == 0) {
            head = head.next;
            return true;
        }
        int i = 1;
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (i == index) {
                preNode.next = curNode.next;
                return true;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        return false;
    }

    public int length() {
        int length = 0;
        Node tmp = head;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        return length;
    }

    public void printLink() {
        Node tmp = head;
        while (tmp != null) {
            System.out.print(tmp.data + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLink myLink = new MyLink();
        myLink.addNode(0);
        myLink.addNode(1);
        myLink.addNode(2);
        myLink.addNode(3);
        myLink.addNode(4);

        myLink.deleteNode(2);

        myLink.printLink();
    }
}

递归实现链表反转

// 递归实现链表反转
public class LinkDemo {

    class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node reverseNode(Node node) {
        return reverseNode(node, null);
    }

    private Node reverseNode(Node head, Node newNode) {
        if (head == null) {
            return newNode;
        }

        Node next = head.next;
        head.next = newNode;
        newNode = head;
        return reverseNode(next, newNode);
    }
}