链表结构
链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为结点。链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的线性表称为链表
链表类型
根据链表的构造方式的不同可以分为：
- 单向链表
- 单向循环链表
- 双向循环链表
单链表
单链表是构成链表的每个结点只有一个指向直接后继结点的指针。单链表的表示方法，单链表中每个结点的结构：
image.png
单链表结构
单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。
image.png
节点类
单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。设计操作
- 头结点的初始化
- 非头结点的构造
- 获取该结点指向的下个结点
- 设置该结点指向的下个结点
- 设置该结点的数据
- 获取该结点的数据
顺序表和单链表的比较
顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。
和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。 单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。
单链表的效率分析
在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：
image.png
删除单链表的一个数据元素时比较数据元素的平均次数为：
image.png
因此，单链表插入和删除操作的时间复杂度均为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;
}
/**
* 获取当前对象的前一个节点，将当前节点定位到要操作节点的前一个元素，思考
* @param index
* @throws Exception
*/
private void index(int index) throws Exception {
// 小于-1，以首元节点索引为0，头节点为-1
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 {
// TODO Auto-generated method stub
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) + " ");
}
}
}
网友评论