arraylist初始化,java单链表实现

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

今天制作了《剑指offer》的编程问题“从末尾打印链表”。 具体要求如下。

输入链表，并从链表末尾开始按顺序返回ArrayList。

首先考虑的是遍历链表两次，第一次遍历链表元素的个数count。 接下来，定义ArrayList变量。 因为ArrayList是动态数组，所以不能在没有初始化的情况下将指定的值插入到任意位置。 因此，只能首先进行初始化，将count个ArrayList要素代入初始值0。 然后，倒算通过遍历第2次链表而获得的值的位置I，将ArrayList中相应的位置I的值设定为该遍历值。 后来，我发现其他人大多是用递归来做的。 递归原理是堆栈，因为它是先进的后继者，所以最后实现的堆栈的输出顺序正好是从末尾到末尾的顺序。 时间的复杂性比我的方法好。

通过解决今天的问题，我发现我不太熟悉Java的单链表操作和java.ArrayList ) )的特性，所以我想把今天收集的资料记录下来，让自己能记住清楚。

Java对单链表的基本操作：

链表是一种常见的数据结构，链表与数组不同，存储位置可能不连续。 因此，如果想找到链表中指定位置的节点，只能遍历链表。 该数组可以直接从位置找到对应的元素节点，时间复杂度为O(1)。

单链表的结构如下图所示。

按如下方式定义Java链表中的实体类Node :

package com.algorithm.link；

公共类节点{

节点下一步=null；

int val； //节点中的值公共节点(intval )//Node的构造函数

{

this.val=val；

}

}

在Java中使用单链接列表的常规操作：

package com.algorithm.link；

公共类my linked list {

节点头=空； //定义标头节点的指针

/*-------------链表添加节点------------------* /

publicvoidaddnode(intval ) )。

{

节点新节点=新节点(val； //创建要添加的节点

if(head==null )//如果链表为空

{

head=NewNode；

返回；

}

如果else { //链表不为空，找到链表的最后一个节点，然后插入要插入的节点

节点tmp=head；

wile(tmp.next！=空)

{

tmp=tmp.next；

}

tmp.next=NewNode； //此时，tmp是链表的末尾节点

}

}

/*------------链表删除节点--------------* /

publicbooleandeletenode (索引) )。

{

说明if(index==1)//删除的是头部节点

{

head=head.next；

返回真；

}

int i=2；

//链表是两个以上的节点，因此定义前节点和当前节点，分别指向目标节点的前节点和目标节点

节点前节点=head；

节点curnode=head.next；

while(curnode！=空)

{

找到要删除的if(index==I )//节点。 此时，curNode指向该节点

{

preNode.next=curNode.next； //删除节点

返回真；

}

//preNode和curNode节点分别向后移动一个

preNode=preNode.next；

curNode=curNode.next；

I；

}

返回真； //如上所述，您一定可以找到要删除的节点。 此语句不执行。 只是为了让程序可以编译。

}

}

Java.util.ArrayList:

ArrayList是一个动态数组，可根据元素的增加动态重新定位区域，是Array的复杂版本。

ArrayList相对于Array具有以下优点：

可以动态增加或减少元素

实现了ICollection和IList接口

可以灵活地设置数组的大小

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

public ArrayList();

默认的构造器，将会以默认(16)的大小来初始化内部的数组

public ArrayList(ICollection);

用一个ICollection对象来构造，并将该集合的元素添加到ArrayList

public ArrayList(int);

用指定的大小来初始化内部的数组

在构造ArrayList时，可以指定ArrayList的类型，例:ArrayList a = new ArrayList();或ArrayList b = new ArrayList();但指定的类型必须为构造器类型(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[] toArray(T[] a) 方法能够将ArrayList类型数组转换为普通Array数组，例如我们定义了一个Integer 类型的ArrayList数组: ArrayList a = new ArrayList() 并在其上通过循环，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 list=Arrays.asList(array); //将String数组array转化成List

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

ArrayList c = new ArrayList(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