Java链表基本操作和Java.util.ArrayList

Java链表基本操作和Java.util.ArrayList

今天做了一道《剑指offer》上的一道编程题“从尾到头打印链表”，具体要求如下：
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
一开始我想的是通过两次遍历链表，第一次遍历得到链表元素的个数count。然后定义一个ArrayList 变量，由于ArrayList是动态数组，不能在未初始化的情况下对任意位置进行插入指定的值。所以只能先对其进行初始化，将count个ArrayList元素赋值为初始值0。随后第二次遍历链表，将遍历得到的值，按照倒序计算出位置i，将ArrayList对应位置i的值设定为该遍历值。后来发现别人大多都是用递归来做的，因为递归的原理是堆栈，先进后出，所以最后实现的堆栈输出顺序正好是从尾到头的顺序。时间复杂度比我的方法要优。

通过今天的做题，发现自己对于Java对单链表的操作以及java.ArrayList()的一些特性不太熟悉，所以想把今天收集到的资料记录一下，让自己能够记得清楚一些。

Java对于单链表的基本操作：

链表是一种常见的数据结构，链表不同于数组，其存储的位置可能不是连续的。所以当我们想要在链表中查找指定位置的结点时，只能去对链表进行遍历。而数组则直接能够通过位置找到相应的元素结点，时间复杂度为O（1）。
单链表的结构如下图所示：
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAoMAAAAvCAYAAACYL8AyAAAT1UlEQVR4Ae2cZ6wcNReGnfDBD5LQFAhFgIBQRG+iiB6E6ITeRBMQivhB7yB67xJVCYheJVoQnVBEF72JEkCA4BI6hPwBiXx6DGfGd7bcuzs7dd8j7V3P2OOxXx+f8/rYe0fMnj17tpMIASHQEQKTJk1y06dP7+iZuhYeP358bbGgb5MnT67r0KlfQkAICAGPwP/qgoOcczyScs4xFlmlIILTpk3LqvpK1TthwoTaYkHfJEJACAiBuiNQGzIo5xyrqpxzjIVSQiAtAgMDA27OOed0Y8eOTVuVni8JAgoexAOh4EGMRT+nakMG+3kQ+63vcs79NuLF9/fvv/8uvhFqQc8QUPAghlLBgxiLfk6JDNZ09Ot+FLQMzrnuGHcyNYRFJ2iprBAQAnkhoODB8JCuFRmUQxreoKuUEBACQqDfEZC/iDWg7liUIXgQo13OVK3IYDkhVquEQP0RqLszqf8IqodCQAj0MwK1IoNySLEqC4sYi6xSwjgrZFWvEBACQkAI5IlArchgnsDpXUJACAgBIVBdBLSYi8dOWMRY9GtKZLBfR179To2ADGgMobCIsVBKCAgBIVA1BGpFBuWQYvUTFjEWSgkBISAEhIAQEAKtEagVGWzdTeUIASEgBISAEIgR0IJZWMQIKCUyKB0QAl0iIGcSAycsYiyUEgJCQAhUDYFakUE5pFj9hEWMhVJCQAgIASHQGgH5i9bY9EtOrchgvwya+ikEhIAQEALpEBABSoefnq4XAiKD9RrPqDcydBEUmSWEcQxtkVj8+eefbvTo0XFjlBICQkAICIGOEBjZUemSF8Yh6TO7kFHCIX///ff+3S+88ELbNnz22Wdt85UpBIZC4K233nJ33nmnL3buuec69A9BB0P94nr33XcfVF347KAMXfQVAvIV//pLBr2uWPSVQqfsbCXIoJGMlH3V4xki8Omnnzo+yCuvvBK96ZFHHomcNjdx1JdddlmUTwLnTLmyyC+//OL++uuvQpsDuQEXPlWQds4EvQjz33zzzUHXYV4n6eWXX97NnDnTzTfffL6+6667zl155ZXujz/+iOqfNm2a22yzzdzzzz/v9dDq51lLt/uuAvZqoxCoGgIXXXSRbzK+vZ3tx18kgwtc2+Kvav0uc3tTkUGMeijJ6zBvOOmdd97ZXXPNNQ1Fp0+f7vbff3/3+uuvN+SFN9oZ9bR5OJMLL7zQf0inrS/L58GkVf04T5xmmE+/wutu06NGjfJOl+cNLxwzztjqfPrpp91qq63mHXPYjkUWWSQqY2WbfYfjnVWaLUf07eabb3YQw1bSrH29unf11Ve7e++91z355JMev5NOOqktPoceeqgbGBhoW6ZXbUvW0wof7kNmd9ppp0EGf7/99mv3SEPe9ddfP+j5u+66y9sC7MHtt9/uy0M4DzvsMHfBBRe4MWPGRHW89957/v5yyy3n9tprr+h+lRJyfK1HS9i0xqbMOb/++qtv3sILL+w+/PBDn4bkEcUPx/T+++9v6AbBhioeC4HHlFm6JoMQv7XXXtsZAUxed9PpDz74wP3+++8Nj2644YZeQU488UR39NFHuyJARQGXWGIJt8UWW7jHHnvMTZgwoaGd4Y099thj0HZVmFdkGqcJ0bCVGW257bbbOmoSz+KgTZjEn3zyif/YJF1zzTUd44UD/u6776yo++qrr7xzXmyxxfx3lPFfogxR4Lnmmsutvvrq7pZbbvHtp79ff/11sqmZX++2224eQ6JbGE/DHLxpE98IxpNxffbZZyNDCmGiTLhlmnmDW7yA+Xv55Zc3zaV9YV+IEpgOkMcHnXnppZeivqBT66yzjv/ss88+vl50zCKpRJ7BhnqIGlL/kUce6cCE+iGRfEhDIEPn07SRBd9EH1mcPP744wW3pHyvB5tJkyZ1hU1yUdPLa0iNfTjOMFTdRS3kaBfSqn0s2MOFKHaGhWer8s3u84zdJxjBNfYMXOANpC0wcM899/h7Vp58OAFlw3osf6jvMmksNmc4Qa2i2tw1GRyqwc8995w7//zzo5U75VnFcy+M/jEJkuWa1W3k65133vGTHwPfLmrTrI6099haguQQfdhyyy3dySef7KvkG/Jn1zgiVjs33XSTd0o4NJwOZcyhp21Lmue3335798QTTzR1grSPdoIvEjpqnCl9w+lCPKwvG2+8sQMbPsi8887rzjvvPP8sz1sdPLfqqqv6+iHXzZwzBKwMznncuHG+L2wX44SZxJBbJnQRcsghh/hIIboEdixKmEdgCK4//PCDIwpGmnvI+uuv76NyRq6KaDfvXGqppRyROdMpawdk7LTTTvN9wdhzPc8883jiRhmcDhHjL774wn+eeeYZe9QvMJ566ikfDWVcFl100Shv7733dujkG2+84ccMTHAykMjtttsuIpKk0WFbwEQVlCwB4VlxxRU9fvRBpDAeoDJjg85dddVVfpcE+99K0E90towCEXvttdcim2JkrpO2Mo/pI8JcW3bZZd3888/v5yP+lAUb+DBnkY8++sh/Y+uOOOIIt+mmm/rFOM+Fgp/AZlRFttpqK9+PIoNa7bBK/Wviu+++2xMLC/vyMkjf2Wef7Q444AB3ww03uHfffdftueeejpAv0UQmyNtvv+2mTJniNtlkE4fjXXDBBaOVf7MGm3O2PAwiEROM46677mq3c/vGGR933HGeuGy99dZekSGDOBeiFQsttJAnPig7E+HMM890hMQhtZtvvrmfELk1NvEiJh9klvYboaMIaaIwGDHSOG9IEIaKcXzwwQd9HpFRhH6YQJIwHCg6jj90sBBIJjo4MF7UQzlICpiYoQArHHS3QsS4FZFkEdFMZs2a1TTS3GyhQR/5ECEuSjCIYAdmSy+9tDcuYIq+EUkEQxPKcJ+oGTgXKZdeeqnbYYcdvHG3dhCR3nHHHf0ldoDoIXMaYsg8IeKDHlmfzKHaNwQZPNDTlVZayar1kW5boOAsfvzxR1/myy+/HKTv0QMVSHC0ApvHnKG/LJqYmziYfhewefjhh0uJDfMOW4o+M3YsUNB7dBKfh61lPFnMsQjnmm+EMsccc0wqm9gL3aANzE3sTCgsOrHlCPOYIANznDlMX4nGc5++4WuYz2Ed+AUWe7/99lsUSIFHsHhEwArB32DbwvLYNo6DhItAX7jEfxZYYAHvO9hlsqAW8xdcyCtaOiaD5lR//vln3/ZXX321oQ8QB4wxhIPBpcwll1ziIxk4Jlb6bCvaFjNno1AKSARC1Cq5+uXsWVKI2mAUp06dmszK7RpnRduZ0PQLomVEiEgZabBAkWkrE4PVVdECocBAsfoyYRzWXXdd3xcmKP2hHOPIua9rr73WF6WPiK3UMF6cC4QgI0SsSDNZ6SvXYMC1OWcMCeTRHLt/cJh/Wq2ix48fH2GfrAqH0UxYZGywwQYNWZC+ZlvDbB8zeVmx5inMF+YH40U0DYLE+BhRCtsCtpzZxKiib2UQ5gF6RMTYBGdHNNNwZsGEgPGLL77oOErQTI499tiGORQuIuzYA/rJh2v0uMqSdBYihfFoJhc6ZcUG30eUy3QV+wupQTchSxBBhGCJLZK5b+XjHuebgnCZXzAbTwsmT57siR9p+oIPYGucoAi2iV/5M/8ox2LQbBX2iWjjqaee6u019td2lSCA1INALtkaxj6AHWWoD/9jdfmCFfrDuJq9o9nJoJZxh266dPzxx7uHHnrIk3DzT+y8stBGwNJko402cjNmzPD+2HiXJ4OcwzOSZ4VbfWOokWWWWcZ/8+u9tdZayxM7on4mRFYgdYSDiQqyckOxJ06c2LC9C5kKBcedjAS+//77XsHCcqSLcs5sUTFBIDd8iFJAoJoJk2PJJZf0BAlMyiKs+CAWobCNaxPTJhz9IsL07bffhkWj9I033jhI0aKMRCJ0zqwQW0XxEo81XBI5QpJ601AwxQ3bqrAqmMRMMM6/mXBeJWvhHSwkMKhEGIiuMy4nnHBCtJoO20HajO8aa6zh5yBtDMtk0eah6iefNls0mWvIIdvCtiBAHzBeLEpuvfVWby/CrWF7B6SfnYWwXzhVDCl1UM7KUgbSic5gn9BBk7CM3Uv73YktTfsunjfig4NlQZokRr14R6/qEDb/bpMaWWq1UAujh73CPm09HI2C8HH0BGG+0X6LYlqQg7m88sor+0h9ONfs/fhKggL4TiM+HKkywot9s50M5jKLYPxP3hHAPHU1DGpdccUVXe88ff755z5YQJDFhGAMAYTkWEAEuR8GpjwZpAGdikX1mj0HmWAQMfYIL3z55Zc9wSNCePDBB3sDbQNsZwgtSoVBSxq15I9GinDOH3/8se8PRBBSh6PCQbNSgZgwGBBjnMzYsWMd5RkE7q+yyioeBzMAWTiicCyGqp/8bbfd1jtdnuOacSGiZGSQNEL7WXFA5Jm0OHC2k1lp0D9+RWxi74WImHDP7nMP58yBYQxHeD9M27NFfTNZEAwW23F5H0UAY37ljRAVQs/Aml/isv1y+OGH+8gf5RCMF+XZljnjjDN8muf4oYUZXV8w5z+829po7bTIHeSQfphDgWyzJUT70R/ajvMI+4zeQICYWyussELUm3Ch8tNPP0X3bcERbk9FmRkkurGlw2kGkdLTTz+9oShHFnbZZRfvqIsc54aGNbmRFTYEMtD/pJQFGyNOLOLQ9X333defO4dcJQUfaMcleI4ASh4ylO0ln61ai96jawQIOCYWCj6D863YePx+qJPUgc9B0Gd7J8c3bHePNEIeASF8EZE06sHn2zP27Qtn8CcrXW1GMukb2+vM4+QOQCddYwEN74KDmBD1Y3EBAQ8Fu8r4hGU73ia2CqmcKIm9JLzmLCDE4qijjvLFCV/iTDH0hCc5Y4dAoDhXiEIx6AcddJD/8YG9I/yGkCAAV4RzXm+99fx29zfffOMWX3xxTwRpD4QGR81A8KsrY9qEyB944AG/giLsTz6MnRVWkqX7juX0h3dbG3kl7bToizlMyC6CE+aHIrQf3FFkDBR9vvjii/1z1EfkirFli8AEZTNJOmeIMnWEErYpvF9EmpUa28RsR4MJfc9bwCeJEW3AINp2UtgmSLqtrrnPtnye0so4E8XjY/k4Az52bUcPrK3YB4R8flhmYk6H+zgJdhusHPYllLB+Fir8OyN7H+VsdyO8Fz5fxnR4hpUfTUAk2EbD8aYRzndzrAcMcUgm/JsvJPzXHpThyI8d67GyRX93i02W4w8ZIlLLMSlsCfaf97FTBhEiGmaBAfwgacpjcxEi2XYeL8t2djJ22KP77rvPP4Ldx44T5aRPkDgWameddZa74447vN9AX7gHIUFnsPHN7BLHWcx2JXdkeBmBF/xvkX6zE5zalQ11FVuOf+HcIHM6reCnQnJn9TW7Z1vDVobvEbPLomlhqxJpnLOB1so5c84AQiJxnmw/+uijtYRim2228YaSzmW1TUzkCWGythL0ra4Yt+pzq/uMSV2xyEPfWuEa3j/nnHP8D516HQWEfENOOMt5yimn+Fey62Nb6uE5IxwIkSsiDc0cTNjePNOQKEhEJ9hk7S/sGAM4hLskXJOH48Z+2UITXIliUxb7w3EJ0tzPmgQRnGnlO2mTtZG2J22j9ZO+YC/D9pJnfSdt/UDXOFNoi1oI5YEHHuhVhv/AQVDBnqM+ol1GFilEIALS3M4++8rcv74wj2NF9r5232AHf2Exiq6GR47aPZdXXteRwbwayHtQSLaShxr8CvDaPGHTu7pEYCg967JaPSYEukKAbTKcCBHWXgskkyM84TEIiB4Om38RFQrHE9jdKBMR5PgQjrWbHwhl6S8s+gx+yfc0y7OxpSyRbz6kw6h6OBa9TifbaPUTWQ/zaBdi95J9CdtLXrNyFvG3PLumXktbHvWFdVLGdgKsjG9QBf4QFeQ8N/0po1SCDKbZRy8j6GqTEKgbAlUzzFXCP8t/ZcSvW/kkxaKE4X37hWJ4r+h0WR1r0bjo/eVDIO2Rjqx7VAkyOFwQ5JBipIRFjEVWKWGcFbKqVwgIASEgBPJEoFZkME/g9C4hIASEgBCoLgJazMVjJyxiLPo1JTLYryOvfqdGQAY0hlBYxFgoJQSEgBCoGgK1IoNySLH6CYsYC6WEgBAQAkKgNQLyF62x6ZecWpHBfhk09VMICAEhIATSISAClA4/PV0vBEQG6zWeUW9k6CIoMksI4xhaYRFjoZQQEAJCoGoI1IoMyiFVTf3UXiEgBISAECgaAfnOokeg+PfXigwWD6daIAT6EwE5k/4c9yr3Wjpb5dFT23uNgMhgrxEtSX0ydNkPhDDOHmO9QQgIASEgBLJHoFZkUM45e4XRG4SAEBACQqBeCMh31ms8u+lNrchgNwDoGSEgBNIjIGeSHkPVkC8C0tl88dbbyo1ArcigJnesbMIixiKrlDDOClnVKwSEgBAQAnkiUCsymCdwepcQEAJCQAhUFwEt5uKxExYxFv2aEhms6chPnDixlj2be+65S9Gv0aNHu7pi3CnAI0aMqC0WZdG3TsdE5YWAEBACnSBQGzIo5xwPOw5sypQpbubMmW7MmDFxhlI9Q2Dq1Km+roGBgZ7VWfWKpG9VH0G1v18RqOvCVou54Wt0bcignHPjoI8cObLxZk3ulKVvtOOff/6pCarpujHHHHOkq6DET5dF30oMUaWapuBBPFwKHsRY9HNqxOyaHRaYMWOGnPN/Go0DGzduXD/rt/ouBISAEGiJgCL7MTSzZs1yo0aNim/UKCVfOPRg1o4MDt1llRACQkAICAEh4JyCB7EWiDDFWPRj6v8tXtu5fZohFAAAAABJRU5ErkJggg==" alt="49fb6e04fce874ce25024c1f5b6a4b13.png" />

下面定义Java链表的实体类Node：

package com.algorithm.link;
public class Node {
Node next = null;
int val; //节点中的值public Node(int val) //Node的构造函数
    {
        this.val = val;
    }
                            }

Java中对单链表的常见操作：

package com.algorithm.link;
public class MyLinkedList{
        Node head = null; //定义头结点指针

        /*-------------链表添加结点------------*/
        public void addNode(int val)
        {
        Node NewNode = new Node(val);//创建要添加的结点
        if(head==null) //当链表为空时
            {
                head=NewNode;
                return;
            }
        else { //当链表不为空时，则先找到链表的尾结点，然后插入待插入的结点
                   Node tmp = head;
                   while(tmp.next!=null)
                   {
                        tmp=tmp.next;
                   }
                  tmp.next=NewNode;//此时tmp为链表的尾结点
             }
        }

        /*------------链表删除结点----------*/
        public boolean deleteNode(int index)
        {
            if(index==1)//说明删除的是头节点
            {
                head=head.next;
                return true;
            }
            int i=2;
            //因为链表不止两个结点，所以定义一个前结点，一个当前结点，分别指向目标结点的前结点和目标结点
            Node preNode = head;
            Node curNode = head.next;
            while(curNode!=null)
            {
                if(index==i)//找到要删除的结点了,此时curNode指向该结点
                {
                    preNode.next=curNode.next;//删除结点
                    return true;
                }
                //preNode和curNode结点分别向后移动一位
                preNode=preNode.next;
                curNode=curNode.next;
                i++;
            }
            return true;//按照前面的一定能够找到待删除的结点，这句语句不会执行，只是为了程序能够通过编译。
        }
}

Java.util.ArrayList:

ArrayList是一种动态数组，可以根据元素增加的情况动态的重新分配空间，是Array的复杂版本。

ArrayList相对于Array有以下几个优点：

• 可以动态的增加或减少元素
• 实现了ICollection和IList接口
• 可以灵活的设置数组的大小

首先构建一个ArrayList，其提供了三种构造方法：

1. public ArrayList(); 
   默认的构造器，将会以默认（16）的大小来初始化内部的数组
2. public ArrayList(ICollection); 
   用一个ICollection对象来构造，并将该集合的元素添加到ArrayList
3. public ArrayList(int); 
   用指定的大小来初始化内部的数组

在构造ArrayList时，可以指定ArrayList的类型，例:ArrayList<String> a = new ArrayList<String>();或ArrayList<Integer> b = new ArrayList<Integer>();但指定的类型必须为构造器类型(component type)

对ArrayList的基本操作：

• add() 增加元素
• remove(Object o) 遍历ArrayList，删除遇到的第一个指定的元素o
  例： a.remove(new Integer(8)) //删除第一个元素值为8的元素
• remove(index i) 根据下标来删除ArrayList中指定位置的元素
• clear() 清除ArrayList中的所有元素
• contains(Object o) 判断ArrayList中是否存在指定值的元素

将ArrayList 转换为Array数组：

ArrayList提供 public <T> T[] toArray(T[] a) 方法能够将ArrayList类型数组转换为普通Array数组，例如我们定义了一个Integer 类型的ArrayList数组: ArrayList<Integer> a = new ArrayList<Integer>() 并在其上通过循环，add了10个元素。此时，我们若想将其转换成为数组可以这样去转换：

Integer[] value=(Integer[])a.toArray(new Integer[a.size()]);

上述返回的数组的长度大小正好为a数组的大小，我们也可以指定new Integer[]里面的数字，当该长度容纳不下待转换的ArrayList元素个数时，该方法会重新依据ArrayList的大小重新分配一个数组，将ArrayList a 中的元素复制到里面并返回。当指定的数目大于a中的元素个数时，也就是数组的空间有剩余。此时，toArray()方法会将剩余的数组部分的元素值都置为 null。

将数组转换为ArrayList：

String数组 array;
List<String> list=Arrays.asList(array); //将String数组array转化成List

但上述的转化方法返回的list无法对其进行修改和增加元素，仿佛是静态固定的。[解释] 所以还可以通过以下的方法去将数组转换成ArrayList:

ArrayList<String> c = new ArrayList<String>(Arrays.asList(array));

此时返回的ArrayList数组可以正常地对其进行操作。

关于数组扩容对ArrayList效率的影响问题：

当我们以默认不带指定大小的构造器去构造一个ArrayList时，默认会将其大小初始化分配为16。在我们使用增加元素的方法之前，例如使用add（）、addAll（）等，都会首先检查内部数组的大小是否够用，如果不够用，则会以当前容量的两倍来重新构建一个数组，并将旧数组的元素copy到新数组中，并丢弃掉旧数组。这种在临界点进行扩容的操作，会比较影响效率。

比如，一个可能有200个元素的数据动态添加到一个以默认16个元素大小创建的ArrayList中，将会经过： 16*2*2*2*2 = 256 四次的扩容才会满足最终的要求，那么如果一开始就以： ArrayList List = new ArrayList( 210 ); 的方式创建ArrayList，不仅会减少4次数组创建和Copy的操作，还会减少内存使用。

另外一种可能发生的情况是，比如我们定义了一个ArrayList数组，且其大小为30，但我们却有31个元素要添加进去，该ArrayList数组则会经过一个扩容容量变为60，这样最后便会有29个元素的存储空间是浪费掉的。此时，我们可以通过 trimToSize 方法去让当前数组的大小变为实际元素个数的大小，还可以提前大致预测一下数组的大小，然后在数组创建之时就指定好大小，这样能够避免去浪费更多的空间。

java.util.Arrays()、java.util.ArrayList()、java数组之间的关系:

Arrays()实现了对数组的一系列操作方法，而ArrayList是动态数组，其大小可以动态变化。

参考文章

• java实现单链表操作 ： https://www.cnblogs.com/bjh1117/p/8335108.html

• java.util.ArrayList() :
  https://www.cnblogs.com/qingchunshiguang/p/6103731.html