链表知识点

链表

无头单链表

链表中的相邻节点在逻辑上连续，在物理(存储地址)上不一定连续。

不像数组，相邻的元素不仅在逻辑上连续在物理上也连续。

链表就是由若干个链表节点构成的对象就称为链表。

单链表：单向链表，默认只能从链表头部遍历到链表的尾部，实际的应用中很少见，太局限，只能从头遍历到尾部。

节点类的定义

class Node {
	int val;//当前节点保存的值
	Node next;//下一个节点的地址
	Node() {}
	Node(int val){
		this.val = val;
	}
	Node(int val, Node next) {
		this.val = val;
		this.next = next;
}

Node类表示的就是每个链表的节点。可以使用构造方法，在节点在创建对象的时候就被赋值。

链表类的定义

由多个Node节点对象组成的实体就是链表对象。

public class {
	private Node head;//定义一个节点类类型的头节点
	private int size;//链表的节点个数
}

用户只需要调用方法对链表进行操作，不需要知道头节点和一共有多少节点，所以都用private修饰当前类可见。

增删改查都应该在链表类中定义。

增加节点

每次新增节点都要新创建一个Node类的对象。

头插法

在链表的头部插入一个新元素，这个新插入的节点为新的头节点，插入位置在逻辑上是固定的，所以参数只有val，val表示当前节点保存的值。

public void addFirst(int val) {
	Node node = new Node();
	node.val = val;
	node.next = head;
	head = node;
	size  ;
}

先创建一个新的节点对象，新节点保存的值等于用户在调用时参数的值，让新节点的下一个地址为上一个头节点地址，如果链表此时为空则head默认为null，就让新节点的下一个地址为null，然后把当前新节点的地址赋给head，让新节点成为新的头节点，最后让size ，表示当前新增一个节点。

指定索引处插入新节点

节点插入位置不固定，方法参数有两个，index为索引，从0开始，凡是有索引为参数的都要判断索引合法性，因为是插入操作，索引值可以等于size，即尾插，若index< 0或index>size则索引非法。

单链表部分->最核心的操作就是找前驱节点，因为单链表只能从前向后操作。

找到待插入位置的前驱，就是让prev引用从头结点开始先走index - 1步，恰好走到前驱节点。

    public void add(int index, int val) {
        if (index < 0 || index > size) {
            System.err.println("索引非法");
            return;
        }
        if (index == 0) {
            addFirst(val);
        }else {
            Node prev = head;
            Node newNode = new Node();
            newNode.val = val;
            for (int i = 0; i < index - 1; i  ) {
                prev = prev.next;
            }
            newNode.next = prev.next;
            prev.next = newNode;
            size  ;
        }
    }

只有头节点需要特殊考虑，其他都属于"中间节点"，包括尾节点，因为它们都有前驱节点，如果index为0则可以复用addFirst方法，否则让prev从head开始，走index - 1步，到达前驱节点位置，新节点的下一跳变为原来前驱的下一跳，而前驱的下一跳被改为新节点的地址，最后size 。

尾插法

在链表最后插入一个节点，同头插一样，插入位置在逻辑上是固定的，参数只有val一个，但是在写完index处插入后，可以直接复用该方法，让index等于size即可。

    public void addLast(int val) {
        add(size ,val);
    }

查询

查询指定值的索引

如果链表中有值为val的节点，则返回该节点的索引，否则，返回-1，因为-1不是合法索引，用来表示无此节点。

    public int getByValue(int val) {
        Node prev = head;
        for (int index = 0; index < size; index  ) {
            if (prev.val == val) {
                return index;
            }
            prev = prev.next;
        }
        return -1;
    }

查询指定索引的值

方法参数为索引，还需要判断索引合法性，与增加节点不同的是，index不能等于size，因为size为节点个数，而索引是从零开始的，相当于size是尾节点的下一个，还没有节点，查询操作没有意义，而查询、修改和删除操作时，index的合法性判断都是一致的，所以我们可以将判断索引合法性抽象成一个方法，并且封装起来，外部不需要知道。

    private boolean isIllegal(int index) {
        if (index < 0 || index >= size) {
            System.err.println("索引非法");
            return true;
        }
        return false;
    }

判断是否非法，如果索引非法则返回true，否则返回false。

    public int get(int index) {
        if (isIllegal(index)) {
            return -1;
        }
        Node x = head;
        for (int i = 0; i < index; i  ) {
            x = x.next;
        }
        return x.val;
    }

如果经过判断索引非法则直接返回-1，否则从头遍历，找到索引处的值并返回。

查询是否包含指定值

在写完查询指定值的索引后，可以直接复用该方法，如果返回值为-1则返回false，否则返回true。

    public boolean contains(int val) {
        return getByValue(val) != -1;
    }

直接返回表达式，如果为真返回的就是true，反之为false。

修改

修改索引为index位置的值为newVal，并将修改前的值返回。

    public int set(int index, int newVal) {
        if (isIllegal(index)) {
            return -1;
        }
        Node x = head;
        for (int i = 0; i < index; i  ) {
            x = x.next;
        }
        int oldVal = x.val;
        x.val = newVal;
        return oldVal;
    }

还是先进行索引合法性判断，从头遍历找到index位置，先保存当前值，然后修改为新值，将修改前的值返回。

删除

删除指定索引的节点

返回删除前的节点值

    public int remove(int index) {
        if (isIllegal(index)) {
            return -1;
        }
        if (index == 0) {
            Node x = head;
            head = head.next;
            x.next = null;
            size--;
            return x.val;
        }
        Node prev = head;
        for (int i = 0; i < index - 1; i  ) {
            prev = prev.next;
        }
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size--;
        return node.val;
    }

还是找前驱节点，只有头节点没有前驱节点，所以需要将头节点单独讨论，如果index为0，则要删除的为头节点，先让x等于头节点的地址，将头节点的下一个节点赋为新的头节点，再将x的下一跳地址置为空，彻底断绝原来头节点与链表的关系，然后让size–，表示删除了一个节点，最后返回x的val值。如果index不为0，则还是需要index从头节点开始，走index - 1步找到待删除节点的前驱，用node将待删除的节点命名，然后将前驱节点的下一跳地址改为待删除地址的下一跳地址，再将node节点的下一跳地址置空，彻底断绝关系，然后size–，最后返回node的val值。

删除指定值的第一个节点

返回是否删除成功，如删除成功则返回true，否则返回false。

    public boolean removeValueOnce(int val) {
        if (head == null) {
            System.err.println("链表为空，无法删除");
            return false;
        }
        if (head.val == val) {
            Node node = head;
            head = head.next;
            node.next = null;
            size--;
            return true;
        }
        for (Node prev = head; prev.next != null; prev = prev.next) {
            if (prev.next.val == val) {
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size--;
                return true;
            }
        }
        return false;
    }

先判断链表是否为空，若链表为空则直接返回false，空链表无法进行删除操作。

若链表部位空，还需要把头节点单独讨论，如果头节点的值就是待删除的值，则需要更换头节点，size–并返回true，表示删除一个节点成功。

若头节点不是待删除的节点，则定义一个前驱节点从头节点开始遍历，如果前驱节点的下一跳节点为待删除的节点，则让待删除节点命名为node，再将前驱节点的下一跳地址改为node的下一跳地址，最后将node的下一跳地址置空，size–，返回true，删除成功。

若遍历到最后，prev已经为最后一个节点时，还没找到值为val的节点，则返回false，表示无此节点，删除失败。

删除指定值的所有节点

    public void removeAllValue(int val) {
        if (removeValueOnce(val)) {
            removeAllValue(val);
        }
    }

可以利用递归，先在判断条件中删除一个节点，利用其返回值来判断删除是否成功，若删除成功则链表中可能还有值为val的节点，则递归继续判断并删除，若在某次返回值为false时，则说明该链表中一定没有值为val的节点，则停止递归，进行依次返回，结束方法。

    public void removeAllValue(int val) {
        while (head != null && head.val == val) {
            // 头节点就是待删除节点
            Node x = head;
            head = head.next;
            x.next = null;
            size --;
        }
        // 头节点一定不是待删除的节点
        // 判空
        if (head == null) {
            // 链表删完了
            return;
        }else {
            Node prev = head;
            while (prev.next != null) {
                // 至少还有后继结点
                if (prev.next.val == val) {
                    // 此时prev.next就是待删除的结点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size --;
                }else {
                    // 只有当prev.next.val != val才能移动prev指针！
                    prev = prev.next;
                }
            }
        }
    }

也可以利用循环来删除所有值为val的节点，如果头节点就是待删除的节点，则头节点的下一个节点也可能是待删除的节点，所以需要对头节点循环删除，并赋下一个节点为新的头节点，直到头节点不为待删除的节点，才对后面的节点进行判断。

如果此时头节点为null，则可以直接返回，不管是删完了所有头节点还是，一个没删，反正现在链表为空，无法进行删除操作。

如果头节点不为空，则让prev从头结点开始进行遍历，但是在遍历过程中，删除一个节点后，删除的节点的下一跳就会变成前驱节点的下一跳，此时不可以移动前驱节点，一旦前驱节点为待删除结点，那就用永远无法删除这个节点了，因为链表只能从前往后操作，删除一个节点后，只能让size–，不移动prev，在下次循环时，如果下一个节点不是待删除节点的话，才让前驱节点后移，保证前驱节点永远不会等于待删除节点。

带头单链表

单链表的头节点总是需要单独去考虑，是因为只有头节点没有前驱节点，现在引入新的概念为虚拟头节点——dummyHead，只作为链表的头节点使用，不存储有效数据，现在链表中的所有其他有效节点全都可以一视同仁，因为一定都有前驱节点。

public class LinkedListWithHead {
    private int size;
    private Node dummyHead = new Node();
}

增加节点

    public void add(int index, int val) {
        if (index < 0 || index > size) {
            System.err.println("索引异常");
            return;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i  ) {
            prev = prev.next;
        }
        prev.next = new Node(val,prev.next);
        size  ;
    }

有了虚拟头节点之后，再进行新增节点操作时就可以不用单独考虑头节点了，让前驱节点prev从虚拟头节点开始走，这需要走index步才能到达指定位置的节点前驱，找到前驱后，利用构造方法新建一个节点对象，并赋上当前值为val，当前的后继节点地址为前驱节点的后继地址，最后让size 即可。

删除节点

删除指定索引的节点

    public int remove(int index) {
        if (isIllegal(index)) {
            System.err.println("索引非法");
            return -1;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i  ) {
            prev = prev.next;
        }
        Node node = prev.next;
        int oldVal = node.val;
        prev.next = node.next;
        node.next = null;
        size--;
        return oldVal;
    }

不用判断头节点，让前驱节点从虚拟头节点开始，找到待删除节点的前驱节点，删除后size–，返回删除前的值。

删除指定值的所有节点

    public void removeAllValue(int val) {
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size--;
            }else {
                prev = prev.next;
            }
        }
    }

同样不用对头节点进行额外判断，一个循环即可。

双向链表

对于该链表中的任意节点，既可以通过该节点向后走，也可以通过该节点向前走。

双向链表在实际工程中应用非常广泛，是使用这个链表的结构的首选。

双向链表节点类的定义

class DoubleNode {
    DoubleNode prev;
    int val;
    DoubleNode next;

    public DoubleNode() {}

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

    public DoubleNode(DoubleNode prev, int val, DoubleNode next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }

双向链表的节点不仅保存了后继节点的地址，还保存了前驱节点的地址。这使得双向链表中任意节点都可以往前走或往后走。同样也可以使用构造方法再创建对象的时候进行赋值。

双向链表类的定义

public class DoubleLinkedList {
    private int size;
    //头节点
    private DoubleNode head;
    //尾节点
    private DoubleNode tail;
}

size表示节点个数，head表示链表头节点，tail表示链表尾节点。

增加节点

头插法

    public void addFirst(int val) {
        DoubleNode node = new DoubleNode(null,val,head);
        if (head == null) {
            tail = node;
        } else {
            head.prev = node;
        }
        head = node;
        size  ;
    }

在创建节点对象时直接调用有参构造，将节点的上前驱地址置为null，后继地址置为头节点，然后对链表进行判空，如果链表的头节点为空，则表示当前链表为空链表，则需要把该节点同时置为尾节点，如果链表不为空，则需要将新增的节点地址赋给头节点的前驱，然后无论链表是否为空，都应该将新增的节点变成头节点，最后size ，节点个数加一。

尾插法

public void addLast(int val) {
    DoubleNode node = new DoubleNode(tail,val,null);
    if (head == null) {
        head = node;
    } else {
        tail.next = node;
    }
    tail = node;
    size  ;
}

与头插法同理，在创建节点时，前驱置为当前的尾节点，值为val，后继为空。

指定索引插入

在双向链表中查询指定索引不需要都从前向后遍历，也可以从后向前进行查找，不同的查找方式依据的就是索引的位置。

    private DoubleNode node(int index) {
        DoubleNode x;
        if (index < size / 2) {
            x = head;
            for (int i = 0; i < index; i  ) {
                x = x.next;
            }
        } else {
            x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
        }
        return x;
    }

当索引位置<size/2时，则从前向后找快，否则从后向前找更快。

public void add(int index, int val) {
    if (index < 0 || index > size) {
        System.err.println("索引非法");
        return;
    }
    if (index == 0) {
        addFirst(val);
        return;
    }
    if (index == size) {
        addLast(val);
        return;
    }
    DoubleNode prev = node(index - 1);
    DoubleNode node = new DoubleNode(prev,val,prev.next);
    node.next.prev = node;
    prev.next = node;
    size  ;
}

在双向链表中也一样，只要需要索引则需要对索引的合法性进行判断，在插入的位置索引为0或者size时，需要考虑头节点和尾节点的变化问题，所以直接对已经写好的头插和尾插进行复用，再利用私有的方法找到待插入节点，进行插入操作，最后size 。

删除节点

在删除节点前，先定义一个私有方法，作用是输入某一节点地址将其断开连接，并将节点个数减一。

    private void unlink(DoubleNode node) {
        DoubleNode prev = node.prev;
        DoubleNode next = node.next;
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            node.prev = null;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }
        size--;
    }

在之后的删除过程中，找到节点位置复用该方法即可。

这篇好文章是转载于：学新通技术网