链表结构
链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为结点。链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的线性表称为链表
链表类型
根据链表的构造方式的不同可以分为：
单向链表单向循环链表双向循环链表
单链表
单链表是构成链表的每个结点只有一个指向直接后继结点的指针。单链表的表示方法，单链表中每个结点的结构：
单链表结构
单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。
节点类
单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。设计操作
头结点的初始化非头结点的构造获取该结点指向的下个结点设置该结点指向的下个结点设置该结点的数据获取该结点的数据
顺序表和单链表的比较
顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。
和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。 单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。
单链表的效率分析
在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为： 删除单链表的一个数据元素时比较数据元素的平均次数为： 因此，单链表插入和删除操作的时间复杂度均为O（n）。另外，单链表取数据元素操作的时间复杂度也为O（n）。
单链表实现
单链表节点数据结构
package com
.algorithm
.list
;
public class ListedNode {
Object element
;
ListedNode next
;
public ListedNode(ListedNode next
){
this.next
= next
;
}
public ListedNode(Object element
, ListedNode next
){
this.element
= element
;
this.next
= next
;
}
public void setElement(Object element
) {
this.element
= element
;
}
public Object
getElement() {
return element
;
}
public ListedNode
getNext() {
return next
;
}
public void setNext(ListedNode next
) {
this.next
= next
;
}
@Override
public String
toString() {
return this.element
.toString();
}
}
单链表实现
package com
.algorithm
.list
;
import java
.time
.temporal
.Temporal
;
public class LinkList implements List {
private ListedNode head
;
private ListedNode current
;
private int size
;
public LinkList() {
this.head
= current
= new ListedNode(null
);
this.size
= 0;
}
@Override
public int size() {
return this.size
;
}
private void index(int index
) throws Exception
{
if(index
< -1 || index
> size
- 1){
throw new Exception("参数错误");
}
if(index
== -1){
return;
}
int j
= 0;
current
= head
.next
;
while(current
!= null
&& j
< index
){
current
= current
.next
;
j
++;
}
}
@Override
public void insert(int index
, Object obj
) throws Exception
{
if(index
<0 ||index
>size
)
{
throw new Exception("参数错误！");
}
index(index
-1);
current
.setNext(new ListedNode(obj
,current
.next
));
size
++;
}
@Override
public void delete(int index
) throws Exception
{
if(isEmpty()){
throw new Exception("链表为空，无法删除!!");
}
check(index
, 0, "参数范围错误");
index(index
- 1);
current
.setNext(current
.next
.next
);
this.size
--;
}
private void check(int index
, int i
, String message
) throws Exception
{
if (index
< i
|| index
> size
) {
throw new Exception(message
);
}
}
@Override
public Object
get(int index
) throws Exception
{
check(index
, 0, "参数范围错误");
index(index
);
return current
.getElement();
}
@Override
public boolean isEmpty() {
return this.size
== 0;
}
public static void main(String
[] args
) throws Exception
{
LinkList list
= new LinkList();
for(int i
= 0; i
< 10; i
++){
int t
= (int) ((Math
.random()*100) % 100);
list
.insert(i
,t
);
System
.out
.print(t
+" ");
}
list
.delete(4);
System
.out
.println("删除之后");
for(int i
= 0; i
< list
.size
;i
++){
System
.out
.print(list
.get(i
) + " ");
}
}
}
关注我
