我们初学者写程序时大多数用的是数组，但是还是有很多时候，用数组实现感觉很麻烦，所以在学习链表以后就会将这些麻烦解决了。现在我们就了解一下链表吧。
数组[非动态数组]与链表同属于数据结构，都有数据结构的基本操作，这些操作我已经在上次的动态数组的实现中说过了。
数组与链表的区别主要表现在以下几方面:
(1) 从逻辑结构角度来看
a.数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减
的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存
浪费。
b.链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方
便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
(2)从物理存储即内存分配上分析
a.数组是连续的内存，对于访问数据，可以通过下标直接读取，时间复杂
度为O(1)，而添加删除数据就比较麻烦，需要移动操作数所在位置后的所有数据，
时间复杂度为O（N）。
b.链表是物理上非连续的内存空间，对于访问数据，需要从头便利整个链
表直到找到要访问的数据，没有数组有效，但是在添加和删除数据方面，只需要知
道操作位置的引用，很方便可以实现增删，与数组比较灵活有效率。
(3)从内存存储角度来看
a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦。
综合以上的一些数组与链表的特点，以及之前我写的动态数组的实现。
1.在有定长，并且查找、修改操作多且插入、删除少的就使用静态数组
2.在没有确定长度，并且查找、修改操作多且插入、删除少的就使用动态数组
3.在没有确定长度，并且插入、删除少且查找、修改操作多的就使用链表
链表的实现基础原理:
注意:
红色为改变的过程、黄色为注意事项、f表示front、d表示data、n表示next
1.增加 
2.插入
3.删除
4.查找
查找的话，只能一个一个遍历查找
5.修改
只有查找到以后，才能改变该结点的值
package LQJ.newer.a1;
/**
* 双向链表
*
* @author Administrator
*
* @param <E>
*/
public class MyNode<E> {
// 初始状态下，链表没有任何结点，头结点为null,尾结点为null
private Node<E> head = null;
private Node<E> last = null;
//链表长度
private int size = 0;
/**
* 增加结点
* @param e 结点的值
*/
public void add(E e) {
// 根据数据创建结点对象
Node<E> node = new Node<E>(e);
// 如果已经有结点，就将node作为last的下一个结点
if (last != null) {
last.lastnetx = node;
node.frontnetx = last;
last = node;
} else {
head = node;
last = node;
}
size++;
}
/**
* 在某下标出插入某一节点(重载的增加方法)
* @param index 下标
* @param e 结点的值
*/
public void add(int index, E e) {
// 构造新结点
Node<E> node = new Node<E>(e);
// 找到index位置的结点
Node n1 = getNode(index);
if (n1.equals(head)) {
head.frontnetx = node;
node.lastnetx = head;
node.frontnetx = null;
head = node;
} else {
// 找到index-1位置的结点
Node n2 = n1.frontnetx;
n2.lastnetx = node;
node.frontnetx = n2;
n1.frontnetx = node;
node.lastnetx = n1;
}
size++;
}
/**
* 根据下标删除结点
* @param index 下标
*/
public void delete(int index) {
Node<E> nod = getNode(index);
//头结点与尾结点特殊处理
if (nod.equals(head)) {
Node<E> n = getNode(index + 1);
n.frontnetx = null;
head = n;
} else if (nod.equals(last)) {
Node<E> n = getNode(index - 1);
n.lastnetx = null;
last = n;
} else {
//找到index的前一个结点与后一个结点
Node n1 = getNode(index - 1);
Node n2 = getNode(index + 1);
//引用转换
n1.lastnetx = n2;
n2.frontnetx = n1;
}
size--;
}
/**
* 根据值删除结点
* @param e 值
*/
public void delete(E e) {
Node<E> n = head;
Node<E> nn = last;
//该结点的前一个结点
Node<E> n1 = new Node<E>();
//该结点的后一个结点
Node<E> n2 = new Node<E>();
//头结点与尾结点特殊处理
if (n.data.equals(e)) {
n = n.lastnetx;
n.frontnetx = null;
head = n;
} else if (nn.data.equals(e)) {
nn = nn.frontnetx;
nn.lastnetx = null;
last = nn;
} else {
//找到index的前一个结点与后一个结点
while (n != null) {
if (n.data.equals(e)) {
n2 = n.lastnetx;
//引用转换
n1.lastnetx = n2;
n2.frontnetx = n1;
break;
} else {
n1 = n;
n = n.lastnetx;
}
}
if (n == null) {
System.out.println("链表中没有找到" + e);
}
}
size--;
}
/**
* 获得某值的下标
* @param e 值
* @return 下标
*/
private int getindex(E e) {
int index = -1;
Node<E> n = head;
while (n != null) {
index++;
if (n.data.equals(e)) {
break;
}
n = n.lastnetx;
}
return index;
}
/**
* 更新结点的值
* @param index 下标
* @param e 更新后的值
*/
public void update(int index, E e) {
// 找到index位置的结点
Node n1 = getNode(index);
n1.data = e;
}
/**
* 获得某下标的值
* @param index 下标
* @return 值
*/
public E get(int index) {
Node<E> node = getNode(index);
return node.data;
}
/**
* 获得某下标的结点
* @param index 下标
* @return 结点
*/
public Node getnode(int index) {
Node<E> node = getNode(index);
return node;
}
/**
* 获得某下标的结点(私有方法)
* @param index 下标
* @return 结点
*/
private Node<E> getNode(int index) {
int t = -1;
if (index >= 0 && index < size) {
Node<E> n = head;
while (n != null) {
t++;
if (t == index) {
break;
}
n = n.lastnetx;
}
return n;
} else {
// 抛出异常
throw new IndexOutOfBoundsException("下标超出边界:" + index + size);
// return null;
}
}
public int size() {
return size;
}
/**
* 直接正向输出
* @param node 头结点
*/
public void printfFromHead(Node node){
//循环输出
// while(node!=null){
// System.out.println(node.data);
// node=node.lastnetx;
// }
//递归输出
if(node!=null){
System.out.println(node.data);
node=node.lastnetx;
printfFromHead(node);
}
}
/**
* 反向输出
* @param node 尾节点
*/
public void printfFromLast(Node node){
while(node!=null){
System.out.println(node.data);
node=node.frontnetx;
}
}
}
/**
* 链式结构内部结点类
*
* @author Administrator
*
*/
class Node<E> {
// 内容
E data;
// 对下一个结点的引用
Node<E> lastnetx = null;
// 对前一个结点的引用
Node<E> frontnetx = null;
public Node() {
}
public Node(E e) {
data = e;
}
}
相关推荐
简单的学生信息管理系统（静态数组和链表实现） 数组和链表.pdf
C语言接口与实现中的内存池实现,还包括书中的其他实现，还有一个静态数组链表的实现。
PHP中数组和链表的区别 从逻辑结构来看 1.、数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标...
对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计...用数组描述的链表，即称为静态链表。在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标CUR。
静态链表的使用 数据结构 C 静态链表 结构体数组
本文实例为大家分享了C++实现基于静态数组的顺序表，供大家参考，具体内容如下 实现的基本操作有： 1. 初始化 2. 尾插 3. 尾删 4. 头插 5. 头删 6.查找任意元素 7. 读任意位置元素 8. 修改任意位置元素 9....
在编这个程序之前 其实在网上搜了很多这方面对于这个方法实现的程序 可没找到 于是自己编了一个 结构思路很容易看清楚 希望对大家有帮助
在静态链表中节点内存的申请与释放都需要自行维护，由于这里是链表，也很容易想到将空余的节点链接起来形成一个free_list，每次需要时从free_list头部取出一个节点，释放时再将节点加到头部，这样就能够非常容易的...
链表是一种动态数据结构，它允许在运行时动态地添加或删除元素，这一点与静态数组不同。链表的优点是能够灵活地管理不同数量和类型的数据，而不受数组大小固定的限制。此外，链表在插入和删除操作时不需要像数组那样...
C++ 实现静态链表的简单实例 用数组描述的链表，即称为静态链表。 在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。 这种存储结构，仍需要预先分配一个较大的空间，但在作为...
栈一般用数组或者链表来实现。数组需要静态分配数据空间，占用空间比较大。链表则根据实际需要动态分配数据空间，占用空间相对小一些。本程序用单向链表实现栈。是C++、数据结构及算法学习的一个小小练习。供大家...
对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。 这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅...
简单的程序 帮你巩固课本学到的知识，提高你的编程能力
有些高级语言没有指针，我们可以用数组来表示单链表，在数组中以整型游标来代替指针。这种用数组描述的链表称为静态链表。
在线段树中，不考虑添加元素，即区间固定，假设区间有n个元素，数组开出4n的静态空间就好了。 AVL树还可以优化，比如在维护平衡之前要判断平衡因子，如果计算的平衡因子与之前保持一致则不需要维持平衡。 最重要的树...
利用C++实现以下经典数据结构与算法：线性表（顺序表、链表、静态链表、三元组）、栈（双栈、共享栈）、队列（任务调度、循环队列、双向队列、链队列）、数组（特殊矩阵、稀疏矩阵压缩）、串（朴素模式匹配、KMP算法...
在前面两篇博客中，我分别使用了静态数组和动态数组来模拟循环队列。但是线性表中和队列神似的莫过于链表了。我在前面也使用了大量的篇幅来讲述了链表的各种操作。我们使用一种比较特殊的链表——非循环双向链表来...
Kmeans算法的C++实现，输入的instance的数据结构有设计为静态数组存储和动态链表存储
顺序表的实现静态数组动态数组2.链表的实现二.栈三.队列四.串StringString StringBuffer 和 StringBuilder五.树和二叉树六.哈希表七. 图邻接矩阵邻接表 一.线性表 1.顺序表的实现 静态数组 java只有在为数组分配变量...
通常情况下，我们使用静态数组来表示顺序表，也可以使用指针动态分配内存来实现动态数组形式的顺序表。 顺序表的特点是支持随机访问，但在插入和删除操作时需要进行元素的移动，因此一些特殊场景下不适合使用顺序表...