Java数据结构之链表及其常见算法

一、什么是链表

       链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

二、链表的分类

2.1 单链表

2.2 双链表

2.3 循环链表

三、代码实现（双链表）

/**
 * @author 17122
 */
public class MyLinkedList<E> implements Iterable<E> {

    private int size;
    /**
     * 改变次数
     */
    private int modCount = 0;

    /**
     * 头结点指针  指向上一个Node的值
     */
    private Node<E> beginMarker;

    /**
     * 尾结点指针    指向下一个Node的值
     */
    private Node<E> endMarker;


    /**
     * 静态内部类
     *
     * @param <E>
     */
    private static class Node<E> {

        public E data; //值

        public Node<E> prev;  //上一个元素值

        public Node<E> next;  //下一个元素值

        public Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    /**
     * 空构造
     */
    public MyLinkedList() {
        doClear();
    }

    /**
     * 清空数组
     */
    private void doClear() {
        beginMarker = new Node<E>(null, null, null);
        endMarker = new Node<E>(null, beginMarker, null);
        beginMarker.next = endMarker;
        size = 0;
        modCount++;
    }

    /**
     * 返回大小
     *
     * @return
     */
    private int size() {
        return size;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加一个元素
     *
     * @param item
     */
    public void add(E item) {
        add(size(), item);
    }

    /**
     * 向一个位置添加元素
     *
     * @param index
     * @param item
     */
    public void add(int index, E item) {
        addBefore(getNode(index, 0, size), item);
    }

    /**
     * 获取一个元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        return getNode(index).data;
    }

    /**
     * 获取一个节点
     *
     * @param index
     * @return
     */
    private Node<E> getNode(int index) {
        return getNode(index, 0, size() - 1);
    }

    /**
     * 获取一个元素
     *
     * @param index
     * @param lower
     * @param upper
     * @return
     */
    private Node<E> getNode(int index, int lower, int upper) {
        Node<E> node;
        //验证是否合法
        if (index < lower || index > upper) {
            throw new IndexOutOfBoundsException();
        }
        //
        if (index < size() / 2) {
            node = beginMarker.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = endMarker;
            for (int i = size(); i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    /**
     * 替换值
     *
     * @param index
     * @param item
     * @return
     */
    public E set(int index, E item) {
        Node<E> node = getNode(index);
        E data = node.data;
        node.data = item;
        return data;
    }


    /**
     * 删除一个元素
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        return remove(getNode(index));
    }

    /**
     * 删除一个节点
     *
     * @param node
     * @return
     */
    private E remove(Node<E> node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        size--;
        modCount++;
        return node.data;
    }

    /**
     * 向头节点添加元素
     *
     * @param node
     * @param item
     */
    private void addBefore(Node<E> node, E item) {
        Node<E> newNode = new Node<>(item, node.prev, node);
        newNode.prev.next = newNode;
        node.prev = newNode;
        size++;
        modCount++;
    }


    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    /**
     * 迭代器内部类
     */
    private class LinkedListIterator implements Iterator<E> {

        private Node<E> current = beginMarker.next;

        private int expModCount = modCount;

        private boolean okToRemove = false;


        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        @Override
        public E next() {
            if (modCount != expModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (modCount != expModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new NoSuchElementException();
            }
            MyLinkedList.this.remove(current.prev);
            expModCount++;
            okToRemove = false;
        }

    }
}

四、常见算法

4.1 合并两个有序链表

问题描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
# 示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
# 示例 2:
输入：l1 = [], l2 = []
输出：[]
# 示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

# 提示：

- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按非递减顺序排列

题解：

   /**
     * 合并两个有序链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //如果l1为空就直接输出l2
        if (l1 == null) {
            return l2;
            //如果l2为空就直接输出l1
        } else if (l2 == null) {
            return l1;
            //比较l1和l2的值
        } else if (l1.val < l2.val) {
            //进行递归操作
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

4.2 删除链表中重复的元素

问题描述：

题目：
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次 。返回同样按升序排列的结果链表

示例 1：
输入：head = [1,1,2]
输出：[1,2]

示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]

题解：

   /**
     * 删除链表的重复元素
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode node = head;
        while (node.next != null) {
            //比较当前元素和下一个元素的值
            if (node.val == node.next.val) {
                //删除操作
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return head;
    }

4.3 旋转链表

问题描述：

给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

题解：

   /**
     * 迭代方式
     *
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        //定义被反转的新链表
        ListNode prev = null;
        //旧链表
        ListNode curr = head;
        while (curr != null) {
            //获取旧链表的下一个节点
            ListNode next = curr.next;
            //旧链表的下一个节点指向新链表
            curr.next = prev;
            //将旧链表复制到新链表
            prev = curr;
            //将旧链表更新为旧链表的下一个节点
            curr = next;
        }
        return prev;
    }

    /**
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        //递归的终止状态
        //等于空或只有一个值则返回原链表
        if (head == null || head.next == null) {
            return head;
        }
        //进行递归
        ListNode newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

部分内容来源自力扣：https://leetcode-cn.com/