单向链表思路

单向链表思路

package linkedList;

import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.function.Consumer;

public class oneWaylinkedList implements Iterable {
    
    public static class Node {
        public int data;

        public Node next;

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

    private Node first = null;

    private Node current = null;

    
    public void add(int data) {
        //产生一个新节点
        Node node = new Node(data);
        //1、如果是第一个节点
        if (Objects.isNull(first)) {
            first = node;
            current = node;
        } else {
            //2、如果不是第一个节点
            current.next = node;
            current = node;
        }
    }

    
    public void del(int position) {
        //如果要删除的是头节点
        if (position == 0) {
            first = first.next;
        }
        int curPosition = 1;
        Node preNode = first;
        Node curNode = first.next;
        while (Objects.nonNull(curNode)) {
            if (curPosition == position) {
                preNode.next = curNode.next;
                //清空要删除节点的next
                curNode.next = null;
            }
            curPosition++;
            preNode = curNode;
            curNode = curNode.next;
        }
    }

    
    public void display() {
        Node node = first;
        while (Objects.nonNull(node)) {
            System.out.println(node.data);
            node = node.next;
        }
    }

    
    public Node getStartNode() {
        return first;
    }

    
    public Node getEndNode() {
        if (Objects.isNull(first)){
            return null;
        }
        Node node = first;
        while (Objects.nonNull(node.next)) {
            node = node.next;
        }
        return node;
    }

    
    public Node get(int position) {
        if (position == 0) {
            return first;
        }
        int curPosition = 1;
        Node curNode = first.next;
        while (Objects.nonNull(curNode)) {
            if (curPosition == position) {
                return curNode;
            }
            curPosition++;
            curNode = curNode.next;
        }
        return null;
    }

    @Override
    public Iterator iterator() {
        //匿名内部类
        return new Iterator() {
            Node node = first;//外部类中的私有成员

            @Override
            public void remove() {
                Iterator.super.remove();
            }

            @Override
            public void forEachRemaining(Consumer action) {
                Iterator.super.forEachRemaining(action);
            }

            @Override
            public boolean hasNext() {
                return Objects.nonNull(node);
            }

            @Override
            public Object next() {
                int data = node.data;
                node = node.next;
                return data;
            }
        };
    }

    @Override
    public void forEach(Consumer action) {
        Iterable.super.forEach(action);
    }

    @Override
    public Spliterator spliterator() {
        return Iterable.super.spliterator();
    }

}

图解：

思路：首先要理解一个节点包含两部分，其中data是数据，next是指向下一个节点。故链表的数据连接起来其实是通过next。知道了节点的含义及内容后，我们可以去写一个Node类封装节点 。再建一个类去编写链表，其实链表只需要知道头节点和当前节点。也就是说我们向链表插入第一个节点a时，a既是头节点也是当前节点，继续向链表插入节点b时，a依旧是头节点，但是此时我们需要做两个 *** 作，第一个是将节点a中的next指向节点b，第二个是更改当前节点为b。以此类推便形成了单向链表，所以链表中最后一个节点的next是null，没有指向了。

*** 作：链表的增删改查，重点讲一下删除，若链表此时是a—b—c—d四个节点，想要删除节点c，那么需要直接更改节点b的next，将其指向节点d并将节点c的next致空。