java数据结构YZP专栏-----链表

1. 线性数据结构，和数组不同，数组要求元素类型一致，大小固定（满了需要扩容），内存地址连续
2. 链表，每一个结点都会存储下一个结点的地址，双向链表还会存储上一个结点的地址。结点类型不固定，大小不固定，内存地址无需连续。只要我们知道固定某一结点的位置(例如单链表头结点，双链表头尾均可，中间位置一般没人那么干)，就可以找到所有元素。

文章目录

• • 1. 单链表实现（Single linked list implementation）
  • 2. 双链表实现（Double linked list implementation）
  • 3. 循环链表实现（Circular linked list implementation）

1. 单链表实现（Single linked list implementation）

1. 每个结点，拥有存储数据的数据域data和指向它后继（下一个结点）的指针域next
2. head变量保存头结点，最后一个结点的next指向空

1. 查询：对比数组效率低，需要从头结点依次遍历
   
2. 修改：对比数组效率低，从头结点依次遍历，找到目标结点后，修改结点数据域
   
3. 插入：对比数组效率高，按照最复杂的情况，从头结点遍历到需要插入位置，让自己的next=原来这个位置的结点，让前面的结点的next指向自己

1. 尾部插入，直接让原来的尾结点的next指向自己，自己的next指向null
   
2. 头部插入，让自己的next指向原来的head头结点。然后head指向自己，自己成为新的头结点
   
3. 中间插入，假设插入3这个位置，让自己next指向3这个位置当前的结点，然后2位置的next指向自己
   

4. 删除：对比数组效率高

1. 尾部删除，Java中，直接让倒数第二个next指向null，那么尾结点因为没有结点指向，会被垃圾回收器回收
   
2. 头部删除，Java中，让head指向next，也就是头结点后面的元素，此时原来的头结点没有引用指向，会被垃圾回收器回收
   
3. 中间删除，找到要删除结点，直接让前面结点的next越过它指向它的next，此时没有引用指向它，被垃圾回收器回收
   

1. 效果演示
   
2. 代码

import java.util.Collection;
import java.util.NoSuchElementException;

public class SingleLinkedList<E> {
    //内部类，单链表结点
    private static class Node<E> {
        E data;//数据域
        Node<E> next;//后继指针域
        Node(E element, Node<E> next) {
            this.data = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }
    private Node<E> first;//头结点
    private int size = 0;//链表长度
    //构造方法
    public SingleLinkedList(){}
    //用集合构造
    public SingleLinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    //获取指定下标结点
    private Node<E> node(int index){
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }
    //获取指定下标结点
    public E get(int index) {
        checkElementIndex(index);
        return node(index).data;
    }
    //获取首结点
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.data;
    }
    //获取尾结点
    public E getLast() {
        final Node<E> l = node(size-1);
        if (l == null)
            throw new NoSuchElementException();
        return l.data;
    }
    //添加单个节点,默认添加到头部
    public boolean add(E e) {
        linkFirst(e);
        return true;
    }
    //插入指定元素到指定下标处
    public void add(int index, E element) {
        checkPositionIndex(index);//下标index是否合理

        if (index == size)//如果插入位置就是最后一个位置
            linkLast(element);
        else if(index == 0)
            linkFirst(element);
        else//否则插入指定位置的前一个位置
            linkBefore(element, node(index-1));
    }

    //插入元素到指定结点之前
    private void linkBefore(E e, Node<E> pred) {
        final Node<E> newNode = new Node<>(e,pred.next);
        pred.next = newNode;
        size++;
    }
    //插入元素到末尾
    private void linkLast(E e) {
        Node<E> last = node(size);//末尾结点
        final Node<E> newNode = new Node<>(e, null);
        last.next = newNode;
        size++;
    }

    //向头部添加元素
    private void linkFirst(E e) {
        final Node<E> f = first;//头结点
        final Node<E> newNode = new Node<>(e,f);//当前头结点f，为新结点next
        first = newNode;//新结点成为头结点
        size ++;
    }

    //用一个集合来添加
    public boolean addAll(Collection<? extends E> c) {
        return this.addAll(size,c);//默认从尾部添加
    }
    //插入一个列表，到指定位置
    public boolean addAll(int index,Collection<? extends E> c){
        Object[] a = c.toArray();//获取要添加列表
        int numNew = a.length;//保存要添加列表长度

        if (numNew == 0) return false;

        Node<E> pred,succ;//用来保存指定插入位置的结点succ，指定插入位置的前面一个结点pred
        if(size == index){//如果当前插入结点位置就是末尾，那么指定插入位置结点就是null
            succ = null;
            pred = node(size);//获取尾结点，插入位置前面一个结点，就是尾结点
        }else{//如果插入位置是小于size的，succ获取当前插入位置结点，pred获取插入位置结点前一个位置
            pred = node(index-1);//插入位置结点前一个结点
            succ = pred.next;//要插入位置的结点
        }

        //开始批量插入结点
        for (Object o : a){
            E e = (E) o;//强制转换结点为E
            Node<E> newNode = new Node<>(e, null);//封装为结点
            if (pred == null)//如果前驱为null
                first = newNode;//说明是第一次插入结点，为头结点
            else//否则，新结点为pred的后继
                pred.next = newNode;
            pred = newNode;//pred后移
        }
        if (succ != null) {//如果succ不为null，说明是中间插入
            pred.next = succ;//让原来这个元素succ到新插入结点的后面
            //包括succ的next，也会一起到后面
        }

        size += numNew;//长度增加
        return true;
    }
    //删除，单链表，只有拿到要删除元素的前一个结点，才能删除要删除结点
    //移除首结点，直接移除即可
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    //移除尾结点，根据倒数第二个结点，删除倒数第一个
    public E removeLast() {
        final Node<E> l = node(size-2);
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    //移除指定元素，除了头结点，剩下的都需要用前一个删除要删除结点
    public boolean remove(Object o) {

        //如果要删除元素是null，需要使用 == 来比较
        if (o == null) {
            if(first.data == o){//判断是否是首结点
                removeFirst();
                return true;
            }
            //从头遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.next!=null&&x.next.data == null) {//如果要下一个结点是要删除的结点，就执行删除逻辑
                    unlink(x);
                    return true;
                }
            }
        } else {
            if(first.data.equals(o)){//判断是否是首结点
                removeFirst();
                return true;
            }
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.next!=null&&o.equals(x.next.data)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.data;
        final Node<E> next = f.next;
        f.data = null;
        f.next = null; // help GC
        first = next;
        size--;
        return element;
    }
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final Node<E> next = l.next;
        final E element = next.data;
        l.next = null;
        next.data = null;
        next.next = null;// help GC
        size--;
        return element;
    }
    //移除指定结点
    private E unlink(Node<E> x) {
        // assert x != null;
        //x是要删除结点的前一个
        final Node<E> next = x.next.next;//要删除结点的后继
        final E element = x.next.data;//要删除结点的元素

        if (next != null) {//如果要删除结点有后继，表示不是最后一个元素
            x.next = next;//让当前删除元素的前驱x的next执行删除结点的后继
        }else{
            x.next = null;//如果没有后继，则指向null
        }
        size--;
        return element;
    }

    //下标是否合理
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //遍历


    @Override
    public String toString() {
        return "SingleLinkedList{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.add(3);
        list.add(2);//添加元素到头
        list.add(0,0);//插入元素
        list.add(1,1);
        System.out.println("添加&插入元素完成："+list);
        System.out.println("获取头元素"+list.getFirst());
        System.out.println("获取尾元素"+list.getLast());
        System.out.println("获取下标为1元素"+list.get(1));
        list.removeFirst();
        System.out.println("移除头元素"+list);
        list.removeLast();
        System.out.println("移除尾元素"+list);
        list.remove(1);
        System.out.println("移除data为1的元素"+list);
    }
}

2. 双链表实现（Double linked list implementation）

1. 每个结点，拥有数据域data，指向后继的next指针域，以及指向前驱的prev指针域
2. 头结点的前驱为null，尾结点的后继为null

1. 效果
   
2. 代码

package com.yzpnb.data_structures.linked_list.double_linked_list;

import com.yzpnb.data_structures.linked_list.single_linked_list.SingleLinkedList;

import java.util.Collection;
import java.util.NoSuchElementException;


public class DoubleLinkedList<E> {
    //双链表结点
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    transient int size = 0;//链表大小
    transient Node<E> first;//头结点
    transient Node<E> last;//尾结点
    public DoubleLinkedList() {}
    public DoubleLinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    //获取指定下标结点
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    //获取指定下标结点
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    //获取首结点
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
    //获取尾结点
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    //添加单个节点,默认添加到尾部
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    //插入指定元素到指定下标处
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    //插入元素到指定结点之前
    private void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
    //插入元素到末尾
    private void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }
    //向头部添加元素
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
    }
    //用一个集合来添加
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    //插入一个列表，到指定位置
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        return true;
    }
    //移除首结点
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    //移除尾结点
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    //移除指定元素
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        return element;
    }
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        return element;
    }
    //移除指定结点
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        return element;
    }
    //下标是否合理
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        Node<E> node = this.first;
        stringBuffer.append("first={");
        for(;node.next!=null;){
            if(node.prev !=null){
                stringBuffer.append(toStringNode(node.item,node.next.item,node.prev.item)+",");
            }else{
                stringBuffer.append(toStringNode(node.item,node.next.item,null)+",");
            }

            node = node.next;
        }
        if(node.prev!=null){
            stringBuffer.append(toStringNode(node.item,null,node.prev.item));
        }else{
            stringBuffer.append(toStringNode(node.item,null,null));
        }

        stringBuffer.append("}");
        return stringBuffer.toString();
    }
    public String toStringNode(E item,E next,E prev){
        return "Node{" +
                "prev=" + prev +
                ", item=" + item +
                ", next=" + next +
                '}';
    }

    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        list.add(2);//添加元素到尾
        list.add(3);
        list.add(0,0);//插入元素
        list.add(1,1);
        System.out.println("添加&插入元素完成："+list);
        System.out.println("获取头元素"+list.getFirst());
        System.out.println("获取尾元素"+list.getLast());
        System.out.println("获取下标为1元素"+list.get(1));
        list.removeFirst();
        System.out.println("移除头元素"+list);
        list.removeLast();
        System.out.println("移除尾元素"+list);
        list.remove(1);
        System.out.println("移除data为1的元素"+list);
    }
}

3. 循环链表实现（Circular linked list implementation）

1. 可以是单链表，也可以是双链表，只不过最后一个结点的next不指向null，而是头结点
2. 如果是双向链表，除了尾结点next指向头结点，还需要头结点prev指向尾结点

1. 由于只改一个指针指向，就不写代码演示了，只需要让尾结点的next指向头，双向链表，让头结点prev也指向尾结点