数据结构和算法Java描述单链表

单链表的定义
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;单链表采用的是链式存储结构，使用一组地址任意的存储单元来存放数据元素。在单链表中，存储的每一条数据都是以节点来表示的，每个节点的构成为：元素（存储数据的存储单元）+指针（存储下一个节点的地址值），单链表的节点结构如下图所示：&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;另外，单链表中的开始节点，我们又称之为首节点；单链表中的终端节点，我们又称之为尾节点。如下图所示：
根据序号获取结点的操作:
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;在线性表中，每个节点都有一个唯一的序号，该序号是从0开始递增的。通过序号获取单链表的节点时，我们需要从单链表的首节点开始，从前往后循环遍历，直到遇到查询序号所对应的节点时为止。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;以下图为例，我们需要获得序号为2的节点，那么就需要依次遍历获得“节点11”和“节点22”，然后才能获得序号为2的节点，也就是“节点33”。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;因此，在链表中通过序号获得节点的操作效率是非常低的，查询的时间复杂度为O(n)。
根据序号删除节点的操作
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;根据序号删除节点的操作，我们首先应该根据序号获得需要删除的节点，然后让“删除节点的前一个节点”指向“删除节点的后一个节点”，这样就实现了节点的删除操作。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;以下图为例，我们需要删除序号为2的节点，那么就让“节点22”指向“节点44”即可，这样就删除了序号为2的节点，也就是删除了“节点33”。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;通过序号来插入节点，时间主要浪费在找正确的删除位置上，故时间复杂度为O(n)。但是，单论删除的操作，也就是无需考虑定位到删除节点的位置，那么删除操作的时间复杂度就是O(1)。
根据序号插入节点的操作
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;根据序号插入节点的操作，我们首先应该根据序号找到插入的节点位置，然后让“插入位置的上一个节点”指向“新插入的节点”，然后再让“新插入的节点”指向“插入位置的节点”，这样就实现了节点的插入操作。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;以下图为例，我们需要在序号为2的位置插入元素值“00”，首先先把字符串“00”封装为一个节点对象，然后就让“节点22”指向“新节点00”，最后再让“节点00”指向“节点33”，这样就插入了一个新节点。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;通过序号来插入节点，时间主要浪费在找正确的插入位置上，故时间复杂度为O(n)。但是，单论插入的操作，也就是无需考虑定位到插入节点的位置，那么插入操作的时间复杂度就是O(1)。
顺序表和单链表的比较
存储方式比较
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;顺序表采用一组地址连续的存储单元依次存放数据元素，通过元素之间的先后顺序来确定元素之间的位置，因此存储空间的利用率较高
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;单链表采用一组地址任意的存储单元来存放数据元素，通过存储下一个节点的地址值来确定节点之间的位置，因此存储空间的利用率较低。
存储方式比较
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;顺序表查找的时间复杂度为O(1)，插入和删除需要移动元素，因此时间复杂度为O(n)。若是需要频繁的执行查找操作，但是很少进行插入和删除操作，那么建议使用顺序表。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;单链表查找的时间复杂度为O(n)，插入和删除无需移动元素，因此时间复杂度为O(1)。若是需要频繁的执行插入和删除操作，但是很少进行查找操作，那么建议使用链表。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;补充：根据序号来插入和删除节点，需要通过序号来找到插入和删除节点的位置，那么整体的时间复杂度为O(n)。因此，单链表适合数据量较小时的插入和删除操作，如果存储的数据量较大，那么就建议使用别的数据结构，例如使用二叉树来实现。
空间性能比较
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;顺序表需要预先分配一定长度的存储空间，如果事先不知道需要存储元素的个数，分配空间过大就会造成存储空间的浪费，分配空间过小则需要执行耗时的扩容操作。
&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;&nbs;单链表不需要固定长度的存储空间，可根据需求来进行临时分配，只要有内存足够就可以分配，在链表中存储元素的个数是没有限制的，无需考虑扩容操作。
代码实现
定义List接口
ublicinterfaceList{
intsize();
voidadd(Objectelement);
Objectget(intindex);
voidmove(intindex);
voidadd(intindex,Objectelement);
StringtoString();
}SingleLinkedList实现类
ublicclassSingleLinkedListimlementsList{
用于保存单链表中的首节点
rivateNodeheadNode;用于保存单链表中的尾节点
rivateNodelastNode;用于保存单链表中节点的个数
rivateintsize;获取单链表中节点的个数
ublicintsize(){
turnthis.size;
}
**
*添加元素
*@aramelement需要添加的数据
*
ublicvoidadd(Objectelement){
1.把需要添加的数据封装成节点对象
Nodenode=newNode(element);
2.处理单链表为空表的情况
if(headNode==null){
2.1把node节点设置为单链表的首节点
headNode=node;
2.2把node节点设置为单链表的尾节点
lastNode=node;
}
3.处理单链表不是空表的情况
else{
3.1让lastNode指向node节点
lastNode.next=node;
3.2更新lastNode的值
lastNode=node;
}
4.更新size的值
size++;
}**
*根据序号获取元素
*@aramindex序号
*@turn序号所对应节点的数据值
*
ublicObjectget(intindex){
1.判断序号是否合法，合法取值范围：[0,size-1]
if(index<0||index>=size){
thrownewIndexOutOfBoundsExcetion("序号不合法，index:"+index);
}
2.根据序号获得对应的节点对象
Nodenode=node(index);
3.获取并返回node节点的数据值
turnnode.data;
}**
*根据序号删除元素
*@aramindex序号
*
ublicvoidmove(intindex){
1.判断序号是否合法，合法取值范围：[0,size-1]
if(index<0||index>=size){
thrownewIndexOutOfBoundsExcetion("序号不合法，index:"+index);
}
2.处理删除节点在开头的情况
if(index==0){
2.1获得删除节点的后一个节点
NodenextNode=headNode.next;
2.2设置headNode的next值为null
headNode.next=null;
2.3设置nextNode为单链表的首节点
headNode=nextNode;
}
3.处理删除节点在末尾的情况
elseif(index==size-1){
3.1获得删除节点的前一个节点
NodeNode=node(index-1);
3.2设置Node的next值为null
Node.next=null;
3.3设置Node为单链表的尾节点
lastNode=Node;
}
4.处理删除节点在中间的情况
else{
4.1获得index-1所对应的节点对象
NodeNode=node(index-1);
4.2获得index+1所对应的节点对象
NodenextNode=Node.next.next;
4.3获得删除节点并设置next值为null
Node.next.next=null;
4.4设置Node的next值为nextNode
Node.next=nextNode;
}
5.更新size的值
size--;
}**
*根据序号插入元素
*@aramindex序号
*@aramelement需要插入的数据
*
ublicvoidadd(intindex,Objectelement){
1.判断序号是否合法，合法取值范围：[0,size]
if(index<0||index>size){
thrownewIndexOutOfBoundsExcetion("序号不合法，index:"+index);
}
2.把需要添加的数据封装成节点对象
Nodenode=newNode(element);
3.处理插入节点在开头位置的情况
if(index==0){
3.1设置node的next值为headNode
node.next=headNode;
3.2设置node节点为单链表的首节点
headNode=node;
}
4.处理插入节点在末尾位置的情况
elseif(index==size){
4.1设置lastNode的next值为node
lastNode.next=node;
4.2设置node节点为单链表的尾节点
lastNode=node;
}
5.处理插入节点在中间位置的情况
else{
5.1获得index-1所对应的节点对象
NodeNode=node(index-1);
5.2获得index所对应的节点对象
NodecurNode=Node.next;
5.3设置Node的next为node
Node.next=node;
5.4设置node的next为curNode
node.next=curNode;
}
6.更新size的值
size++;
}**
*根据序号获得对应的节点对象
*@aramindex序号
*@turn序号对应的节点对象
*
rivateNodenode(intindex){
1.定义一个零时节点，用于辅助单链表的遍历操作
NodetemNode=headNode;
2.定义一个循环，用于获取index对应的节点对象
for(inti=0;i<index;i++){
3.更新temNode的值
temNode=temNode.next;
}
4.返回index对应的节点对象
turntemNode;
}
节点类rivatestaticclassNode{
**
*用于保存节点中的数据
*
rivateObjectdata;
**
*用于保存指向下一个节点的地址值
*
rivateNodenext;
**
*构造方法
*@aramdata
*
ublicNode(Objectdata){
this.data=data;
}
}ublicStringtoString(){
判断是否为空,如果为空就直接返回[]
if(headNode==null){
turn"[]";
}
StringBuilderstringBuilder=newStringBuilder("[");
Node=headNode.next;
while(!=null){
stringBuilder.aend(.data+",");
=.next;
}
最后一个逗号删掉
stringBuilder.deleteCharAt(stringBuilder.length()-1);
stringBuilder.aend("]");
turnstringBuilder.toString();
}
}Test
ublicclassTest{
ublicstaticvoidmain(String[]args){
1.创建一个对象
Listlist=newSingleLinkedList();
2.添加元素
list.add("11");0
list.add("22");1
list.add("33");2
list.add("44");3
list.add("55");4
删除
list.move(0);
序号添加
list.add(2,"00");
测试get
for(inti=0;i<list.size();i++){
System.out.rint(list.get(i)+"");
}
toString
System.out.rintln(list.toString());
}
}