在分析链表之前,我们先来对之前的动态数组、栈、队列总结一下:
(1)底层依托于静态数组
(2)依靠resize解决固定容量问题
(3)是一种假的的动态数据结构
1.什么是链表
可以从以下两个部分来理解什么是链表
(1)最简单的动态数据结构,是一种真正的动态数据结构;
(2)是一种数据的存储方式,数据存储在"节点"(Node)中
1.1结构基本代码:
class Node{
E e;
Node next;
}
1.2 图示如下:
1.3 优点、缺点
优点:真正的动态,不需要处理固定容量的问题
缺点:丧失了随机访问的能力,也就是不能通过索引进行访问,只能next来进行查找
1.4数组与链表的对比
1.5 基本的链表节点结构代码:
新建一个package(LinkedList),然后新建一个类LinkedList,在该类中封装一个私有的节点,便于后续对于节点的使用。
package LinkedList; public class LinkedList<E> {
//将Node节点设计成私有的类中类
private class Node<E> {
public E e;
public Node next; //两个参数的构造函数
public Node(E e, Node next) {
this.e = e;
this.next = next;
} //一个参数的构造函数
public Node(E e) {
this.e = e;
this.next = null;
} //无参构造函数
public Node() {
this(null, null);
} @Override
public String toString() {
return e.toString();
}
}
}
在本小节中先是简单了解了一下理论知识,然后把基本的链表节点结构使用代码来实现,下一小节我们继续来学习如何如何在链表中添加元素。