我们初学者写程序时大多数用的是数组，但是还是有很多时候，用数组实现感觉很麻烦，所以在学习链表以后就会将这些麻烦解决了。现在我们就了解一下链表吧。
数组[非动态数组]与链表同属于数据结构，都有数据结构的基本操作，这些操作我已经在上次的动态数组的实现中说过了。
数组与链表的区别主要表现在以下几方面:
(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;
}
}
相关推荐
这是一个关于学生信息管理系统的实现，该系统使用了两种数据结构：静态数组和链表。这里主要探讨的是如何用这两种方式来存储和操作学生信息。 首先，我们定义了学生的基本信息结构体`struct P`，包括学生的ID（整型...
数组适合静态存储，动态添加，内存为一连续的地址，查询较快，而链表适合动态存储，扩展性强，只能顺着指针的方向查询，速度较慢。 我们可以得出结论：数组大小固定，不适合动态存储，动态添加，内存为一连续的地址...
"go语言通过数组和链表的方式实现队列" 从给定的文件信息中，我们可以生成以下知识点： 1.队列的定义：队列是一种特殊的线性表，只能在队列的尾部添加元素，在队列的头部删除元素，先进先出（FIFO）。 2.go语言中...
本压缩包文件包含的主题是C语言接口与实现，重点在于内存管理和数据结构的实现，具体涉及了内存池（arena）以及静态数组链表。 首先，让我们深入了解一下内存池（arena）。内存池是一种内存管理技术，它预先分配一...
下面将详细介绍这两种数据结构以及它们的区别。 首先，数组是一种线性数据结构，它将元素在内存中连续存放，每个元素占用相同的内存空间。数组的一个显著优点是通过下标可以直接访问任意元素，具有O(1)的时间复杂度...
集合（链表和数组的区别） 链表和数组是两种基本的数据结构，它们都是集合的实现方式，但是它们在存储和访问方式上有很大的不同。在本文中，我们将详细介绍链表和数组的区别，并讨论何时使用数组、何时使用链表。 ...
数组、链表和集合的区别和应用场景以及堆和栈的区别 数组和集合的区别： 1. 数组的长度是固定的，而集合的长度是动态不固定的。 2. 数组的存储类型是单一的，同一个数组只能存储同一数据类型的数据，而集合可以...
接下来是静态有序数组的实现——`StaticOrderArr`类。这种数据结构主要用于存储已排序的元素，并且其容量固定。由于容量固定，它不支持动态扩容，因此在设计时要考虑如何处理超过容量的插入操作。在实际应用中，这类...
在JavaScript中，ES6之前，Array并非真正的数组，而是基于链表实现，但ES6引入了类型化数组（TypedArray），尽管功能有限，但更接近于传统的数组概念。 链表，作为数组的补充，允许动态地改变其长度。每个链表节点...
在Java编程中，数据结构是基础，而数组和链表是两种常见的线性数据结构。它们各有特点，适用于不同的场景。下面将详细讨论这两种数据结构的区别。 首先，数组是一种静态分配内存的数据结构，其所有元素在内存中是...
有一种用数组来表示的链表，叫做静态链表，它的存储结构就是连续的。 顺序表和数组的区别 ----------------- 顺序表和数组这两个概念容易混淆。顺序表是线性表的一种实现方式，属于物理结构，顺序表是在计算机内存...
数组是一种静态数据结构，它在内存中占据连续的空间，这意味着数组的大小在创建时就已经固定，不能轻易地增加或减少。数组的一个显著优点是它的随机访问能力。由于元素在内存中是连续存放的，可以通过下标直接定位到...
数组和链表是两种基本且重要的数据结构，在编程和算法设计中扮演着核心角色。它们各自具有独特的优缺点，适用于不同的场景。 数组是一种静态的数据结构，它在内存中分配一块连续的空间来存储相同类型的元素。数组的...
而数组则是一种静态的数据结构，其元素可以通过索引来访问，具有随机访问的优点。将数组转换为循环链表意味着数组中的最后一个元素“链接”到第一个元素，形成一个闭合的循环。 在C语言中，我们可以通过设置一个...
Java 中链表和数组的区别 Java 中链表和数组都是数据结构，但它们有着本质的差异。在这篇文章中，我们将探讨链表和数组的区别，並探讨它们各自的特点、优缺点和应用场景。 数组 数组是一种线性结构，可以直接索引...
本资源讲解了链表的基本概念和实现方式，着重介绍了静态链表和动态链表的区别和应用场景。链表是一种常见的数据结构，它由多个节点组成，每个节点都包含一个数据域和一个指向下一个节点的指针。链表的优点是可以动态...
PHP中数组和链表的区别 从逻辑结构来看 1.、数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标...
在本主题中，我们将深入探讨如何使用C语言中的静态数组来实现一个循环队列。循环队列是一种线性数据结构，它巧妙地利用了数组的特性，克服了普通队列在满时无法插入元素、空时无法删除元素的问题。 首先，了解数组...