手写实现单向链表

╰半橙微兮° 2022-02-16 12:14 218阅读 0赞

数据结构对于一个程序员来说是必备的知识，虽然之前也了解过这些数据结构，但是总感觉没有达到一个对所有数据结构都了如指掌的境界，于是作者打算手写实现各种数据结构，以便于学习了解这些数据结构的全貌。

对于数据结构的分析如果足够深入，那么必定还要涉及jvm的内存层面，目前本人还没有足够的知识储备，所以只从代码的层面学习理解这些数据结构的实现。

这次先从最简单的单向链表的实现作为开始，单向链表属于最基础的链表结构，它的定义：*链表是一种物理[存储单元][Link 1]上非连续、非顺序的[存储结构][Link 2]，[数据元素][Link 3]的逻辑顺序是通过链表中的[指针][Link 4]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素][Link 5]的数据域，另一个是存储下一个结点地址的[指针][Link 4]域。——来自百度百科的介绍*

*                                    *![20190422145956371.png][]

链表结构示意图

用我自己的理解来说，链表就是一个个带链接的节点组成的，每个节点由两部分组成，第一部分是该节点存储的数据，第二部分是该节点的下一个节点的指针。这样的结构我们只需要知道这个链表的头节点，那么我们就能挨个得到整个链表的所有节点。

链表的特点：

1.  没有容量限制
2.  没有扩容的需求
3.  操作两头快，中间慢
4.  线程不安全

链表的操作：

1.插入新节点：将插入位置的节点的上一个节点的Next指针赋值给新插入的节点的Next指针，再将上一个节点的Next指针指向新节点。操作完成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70][]

插入新节点示意图

2.删除节点：将要删除的节点位置的上一个节点的Next指针赋值为要删除节点的Next节点指针即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1][]

删除节点示意图

由上面的示意图可知，如果是操作链表的头部和尾部，那么操作速度是最快的，如果是在对链表的中间位置进行操作，将对链表进行遍历操作。

说了一堆废话，下面开始用代码说话

链表的代码实现：

package dataStructure;
    
    import java.util.ConcurrentModificationException;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    import java.util.Objects;
    import java.util.function.Consumer;
    
    /**
     * Created by Viking on 2019/4/7
     * 实现的单向链表的集合
     * 只能从前往后单向遍历
     * 可插入重复元素
     * 实现迭代器遍历集合
     */
    public class MySingleLinkList<E> {
    
        private transient int modCount = 0;
        private transient int size;
        private Node<E> first;
        private Node<E> last;
    
        public void addLast(E e){
            linkLast(e);
        }
        public E removeLast(){
            if (size==0) throw new NoSuchElementException();
           return unlinkLast(last);
        }
        public E remove(int index){
            return unlink(index);
        }
        public E getFirst(){
            return first.item;
        }
        public E getLast(){
            return last.item;
        }
        public E get(int index){
            checkElementIndex(index);
            return node(index).item;
        }
    
        /**
         * 向最后一个元素添加链接.
         */
        private void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
        /**
         * 取消指向最后一个元素的链接.
         */
        private E unlinkLast(Node<E> l) {
            if (first==last&&first!=null) {
                first = null;
                last = null;
            }else if (first!=null) {
                Node<E> node = first;
                int i = 1;
                while (node.next!=null){
                    if (node.next==l&&i==size-1) {
                        node.next = null;
                        last = node;
                    }else  node = node.next;
                    i++;
                }
            }
            size--;
            modCount++;
            return l.item;
        }
    
        /**
         * 取消指定索引的节点
         */
        private E unlink(int index){
            checkElementIndex(index);
            Node<E> cursor;
            if (index==0 && index==size-1){
                cursor = first;
                first = null;
                last = null;
            }else if (index==0) {
                cursor =first;
                first = cursor.next;
            }else if (0 < index && index < size-1){
                Node<E> node = first;
                for (int i =0;i<index-1;i++) node = node.next;
                cursor = node.next;
                node.next = cursor.next;
            }else {
                cursor = last;
                last = node(index-1);
                last.next = null;
            }
            size--;
            modCount++;
            return cursor.item;
        }
        /**
         * 判断指定索引是否存在元素.
         */
        private boolean isElementIndex(int index) {
            return index >= 0 && index < size;
        }
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        /**
         * 返回指定索引的元素.
         */
        private Node<E> node(int index){
            Node<E> node = first;
            for (int i =0;i<index;i++) node = node.next;
            return node;
        }
        /**
         * Constructs an IndexOutOfBoundsException detail message.
         * Of the many possible refactorings of the error handling code,
         * this "outlining" performs best with both server and client VMs.
         */
        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+size;
        }
        public int size(){
            return size;
        }
        public boolean isEmpty(){
            return size==0;
        }
        public String toString(){
            StringBuilder str = new StringBuilder();
            if (first==null){
                str.append("[]");
            }else {
                Node<E> next = first;
                str.append("[");
                str.append(first.item);
                while (next.next!=null){
                    next = next.next;
                    str.append(",");
                    str.append(next.item);
                }
                str.append("]");
            }
            return str.toString();
        }
    
        /**
         * 链表的节点
         */
        private static class Node<E> {
            E item;
            Node<E> next;
    
            Node(E element, Node<E> next) {
                this.item = element;
                this.next = next;
            }
        }
    
        public Iterator<E> myIterator(){
            return new MyIterator(0);
        }
        public Iterator<E> myIterator(int index){
            return new MyIterator(index);
        }
    
        /**
         * 实现迭代器遍历容器
         */
        private class MyIterator implements Iterator<E>{
            private Node<E> lastReturned;
            private Node<E> next;
            private int nextIndex;
            private int expectedModCount = modCount;
            private MyIterator(int index){
                next = index == size ? null : node(index);
                nextIndex = index;
    
            }
            @Override
            public boolean hasNext() {
                return nextIndex < size;
            }
    
            @Override
            public E next() {
                checkForComodification();
                if (!hasNext())
                    throw new NoSuchElementException();
    
                lastReturned = next;
                next = next.next;
                nextIndex++;
                return lastReturned.item;
            }
    
            @Override
            public void remove() {
                checkForComodification();
                if (lastReturned == null)
                    throw new IllegalStateException();
    
                Node<E> lastNext = lastReturned.next;
                unlink(nextIndex-1);
                if (next == lastReturned)
                    next = lastNext;
                else
                    nextIndex--;
                lastReturned = null;
                expectedModCount++;
            }
    
            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                while (modCount == expectedModCount && nextIndex < size) {
                    action.accept(next.item);
                    lastReturned = next;
                    next = next.next;
                    nextIndex++;
                }
                checkForComodification();
            }
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    }

实现方式我是参考了LinkedList的源码，LinkedList是双向链表实现的。

编写一个测试类：

import dataStructure.MySingleLinkList;
    
    import java.util.*;
    
    /**
     * Created by Viking on 2019/4/7
     */
    public class TestSList {
        public static void main(String[] args) {
            MySingleLinkList<String> sList = new MySingleLinkList<>();
            System.out.println(sList.size());
            System.out.println(sList);
            sList.addLast("Hello!");
            sList.addLast("My");
            sList.addLast("Link");
            sList.addLast("List");
            sList.addLast("last");
            sList.addLast("same");
            sList.addLast("same");
            System.out.println(sList.size());
            System.out.println(sList.isEmpty());
            System.out.println(sList);
            System.out.println("index of 0:"+sList.get(0));
            System.out.println("index of 1:"+sList.get(1));
            System.out.println("index of 2:"+sList.get(2));
            System.out.println("index of 3:"+sList.get(3));
            System.out.println("index of 4:"+sList.get(4));
            System.out.println("getFirst:"+sList.getFirst());
            System.out.println("getLast:"+sList.getLast());
            System.out.println(sList);
            System.out.println(sList.removeLast());
            System.out.println("After remove 1 element:size="+sList.size());
            System.out.println(sList.removeLast());
            System.out.println("After remove 2 element:size="+sList.size());
            System.out.println(sList.removeLast());
            System.out.println("After remove 3 element:size="+sList.size());
            System.out.println(sList.removeLast());
            System.out.println("After remove 4 element:size="+sList.size());
            System.out.println(sList.removeLast());
            System.out.println("After remove 5 element:size="+sList.size());
            System.out.println(sList);
            sList.addLast("iterator");
            sList.addLast("is");
            sList.addLast("cool");
            Iterator<String> stringIterator = sList.myIterator();
    //        while (stringIterator.hasNext()){
    //            System.out.println(stringIterator.next());
    //        }
    //        System.out.println(sList);
    
            int i =0;
            while (stringIterator.hasNext()){//一迭代器对象只能执行一次迭代
                System.out.println(stringIterator.next());
                if (i<3) stringIterator.remove();
                i++;
    //            if (sList.size()==1) break;
            }
            System.out.println(sList);
        }
    }

测试结果：

0
    []
    7
    false
    [Hello!,My,Link,List,last,same,same]
    index of 0:Hello!
    index of 1:My
    index of 2:Link
    index of 3:List
    index of 4:last
    getFirst:Hello!
    getLast:same
    [Hello!,My,Link,List,last,same,same]
    same
    After remove 1 element:size=6
    same
    After remove 2 element:size=5
    last
    After remove 3 element:size=4
    List
    After remove 4 element:size=3
    Link
    After remove 5 element:size=2
    [Hello!,My]
    Hello!
    My
    iterator
    is
    cool
    [is,cool]

[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83/8727749
[Link 2]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84/350782
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 4]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304
[Link 5]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[20190422145956371.png]: /images/20220216/9735f5883cd049e180cfc84fea31f079.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70]: /images/20220216/48d9ffd8bf3e4d47a53ec2c50dea9e8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1]: /images/20220216/64a64e4c9e9d42498b390f0fb2cf2811.png