1.什么是链表？
2.链表有哪些特点？
3.为什么要使用链表？
4.链表分为哪几种形式？
直观来说，项链，佛珠，手表都是链表的一种表现形式，链表就是一种由一系列结点构成的数据结构。
链表的特点：链表是由一系列结点构成，每个结点至少包含两个域(数据域和指向下个结点的引用类型)，双向单链表和循环单链表还有个指向父节点的引用类型域。链表中的结点存放的物理地址是非连续的，链表是不定长的，它可以随时加入新的结点。
之前我们用数组实现过队列的方法，既然用数组可以实现，那为什么还要用链表去实现队列的方法呢？数组和链表到底有什么区别？
数组是定长的，数组有下标，这样使得数组查找比较方便，直接通过下标就可得到想要查找的元素，当用数组去实现查找元素操作时，时间复杂度为1，数组中的元素存放的物理地址是连续的，这样就使得数组实现插入和删除的操作比较麻烦，每插入或删除一个元素平均要移动数组中一半的数据元素。然而，链表正好与数组的功能相反，数组的优点正好是链表的缺点，反之亦然。所以，可以根据对数据的不同操作，选择使用这两种方法。当要实现插入或删除操作时，就选择链表，因为链表只需修改指向下个结点引用类型的值，时间复杂度为1.
链表分为线性链表和非线性链表。
线性链表主要包括：单链表，双向链表，循环链表。
非线性链表主要包括：树，图等等。
对单链表的操作：
用链表实现队列的方法：
加入操作：java代码
public void add(Object obj){
if(root==null){//如果队列中还没有结点
root=new LinkNode(obj);//将要添加的作为头结点
end=root;//同时也将尾结点指向头结点
}
else{
LinkNode node=new LinkNode(obj);//先要创建一个结点
end.setNext(node);//将链表串接起来
end=node;//然后在使尾结点移动到该结点上
}
}
求队列的长度：
public int size(){
int count=0;
if(root==null){//如果根结点为空
return 0;//返回0
}
else{//如果根结点不为空，
count++;//计数器+1
LinkNode node=root.getNext();//得到根结点的下一个结点
while(node!=null){
count++;//计数器+1
node =node.getNext();
}
return count;
}
}
根据下标得到一个元素：
public LinkNode get(int index){
int count=0;
if(index>=size()||index<0){//如果给定的值不在范围之内
throw new RuntimeException("你输入已超出范围 index="+index);//抛出异常
}
else{
if(index==0){//如果索引为0
return root;//返回根结点的值
}
else{
LinkNode node=root.getNext();//得到根结点的下个结点
while(node!=null){//如果该结点不为空
count++;//使计数器+1
if(index==count){
return node;
}
else
node=node.getNext();
}
}
}
return null;
}
往队列中插入一个结点：
public void insert(LinkNode node,int index){
if(index<0){//如果插入的位置不准确
throw new RuntimeException("你输入已超出范围 index="+index);//抛出异常
}
else if(index==0){//如果插入的位置为0
node.setNext(root);//将该结点指向根结点就可以了
root=node;//然后在使根结点移动到该结点的位置上
}
else if(index>0&&index<=size()-1){//如果插入的位置既不是队列的头部，也不是队列的末尾
LinkNode node1=get(index-1);//首先要得到插入位置的前一个结点
LinkNode node2=get(index);//还要得到在插入以前该位置的结点
node1.setNext(node);//然后将它们串接起来
node.setNext(node2);
}
else{//如果插入的位置是在末尾
end.setNext(node);//直接将结点插入到队列的末尾
end=node;//将尾结点指向该结点
}
}
将对列中的某个结点删除：
public void remove(int index){
if(index<0||index>=size()){//如果插入的位置不准确
throw new RuntimeException("你输入已超出范围 index="+index);//抛出异常
}
else if(index==0){//如果删除的位置为0
LinkNode node1=root.getNext();//得到根结点的下个结点
root=node1;//将根结点指向该结点
}
else if(index>0&&index<size()-1){//如果删除的位置既不是队列的头部，也不是队列的末尾
LinkNode node1=get(index-1);//首先要得到删除位置的前一个结点
LinkNode node2=get(index);//得到要删除的这个结点
node1.setNext(node2.getNext());//删除位置的前一个结点指向要删除的这个结点的下个结点
}
else{//如果删除的是最后的位置
LinkNode node1=get(index-1);//得到它前面一个位置
node1.setNext(null);
}
}
修改结点的值：
public void xiuGai(LinkNode node,int index){
if(index<0&&index>size()-1){
throw new RuntimeException("你输入已超出范围 index="+index);//抛出异常
}
else {
LinkNode node1=get(index);
node1.setObj(node.getObj());
}
}
双向链表的理解：
双向链表其实跟单链表结构类似，只是比单链表多了个指向父节点的引用类型域而已，所以在建双向链表时，只需将除根结点外的其他个结点的指向父节点的引用类型域指向它的前一个结点即可。
双向链表的操作：
建立一个双向链表：
public static LinkNode creatDoubleLink(String [] a){
LinkNode root=new LinkNode(a[0]);
LinkNode node1=new LinkNode(a[1]);
LinkNode node2=new LinkNode(a[2]);
LinkNode node3=new LinkNode(a[3]);
root.setNext(node1);
node1.setNext(node2);
node1.setParent(root);
node2.setParent(node1);
node2.setNext(node3);
node3.setParent(node2);
return root;
}
遍历双向链表：
public static void printNode(LinkNode root){
if(root.getNext()!=null){
Object obj=root.getObj();
System.out.println("双向链表的数据元素"+obj);
LinkNode node=root.getNext();
printNode(node);
}
else {
Object obj=root.getObj();
System.out.println("双向链表的数据元素"+obj);
LinkNode parent=root.getParent();
while(parent!=null){
Object ob=parent.getObj();
System.out.println("双向链表的数据元素"+ob);
parent=parent.getParent();
}
}
}
向双向链表中插入元素：
public static LinkNode insert(LinkNode nodee,int index){
int count=0;//标记要插入到链表中的哪个位置，根据该标记，找到相应的结点
LinkNode nodeR=creatDoubleLink(root,node);//先得到双向链表的头结点
LinkNode node1=nodeR.getNext();//得到头结点的下个结点
LinkNode last = null;//用来标记最后个结点
if(index<0){//如果插入的位置不符合要求
System.out.println("你插入的位置不对！");
}
if(index==0){//如果要插入到头结点
nodee.setNext(nodeR);
nodeR.setParent(nodee);
nodeR=nodee;
}
else{//如果插入的位置不是在头结点
while(node1!=null){//如果该结点不为空
count++;
if(node1.getNext()==null){//如果是链表的最后一个结点
last=node1;//标记该结点
}
if(count!=index){//如果还没找到要插入的位置
node1=node1.getNext();
}
else {//如果找到要插入的位置了
nodee.setNext(node1);
nodee.setParent(node1.getParent());
node1.getParent().setNext(nodee);
node1.setParent(nodee);
break;
}
}
if(count<index){//如果是插入到链表的末尾
last.setNext(nodee);
nodee.setParent(last);
}
}
return nodeR;
}
删除双向链表中的指定位置的结点：
public static LinkNode delete(int index){
int count=0;//用来标记要删除的是链表中的哪个结点
LinkNode nodeR=creatDoubleLink(root,node);//先得到双向链表的根结点
LinkNode nodee=nodeR.getNext();//得到双向链表根结点的下个结点
if(index==0){//如果要删除的是根结点
nodeR=nodeR.getNext();//将根结点移动到它的下个结点
nodeR.setParent(null);//因为是双向链表，故还需将根结点的父节点设为Null
}
else{//如果删除的不是根结点
while(nodee!=null){
count++;
if(count!=index){//还没找到索引值
nodee=nodee.getNext();//将node往后移，寻找与索引值相同的结点
}
else{
if(nodee.getNext()!=null){//如果删除的不是最后一个结点
nodee.getParent().setNext(nodee.getNext());
nodee.getNext().setParent(nodee.getParent());
}
else{//删除的是最后一个结点
nodee.getParent().setNext(null);
}
}
}
if(count<index){
System.out.println("你要删除的位置不对！");
return null;
}
}
return nodeR;
}
循环链表：当给定一个链表时，判断该链表是否有环。
建立一个循环链表：
public static LinkNode createCircleList(String [] sa){
LinkNode root=new LinkNode(sa[0]);
LinkNode node1=new LinkNode(sa[1]);
LinkNode node2=new LinkNode(sa[2]);
LinkNode node3=new LinkNode(sa[3]);
LinkNode node4=new LinkNode(sa[4]);
root.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
//node4.setNext(root);
return node3;
}
判断循环链表是否有环：
public static boolean isCircle(LinkNode root){
LinkNode fast=root;
LinkNode slow=root;
while(fast!=null&&fast.getNext()!=null){
fast=fast.getNext().getNext();
slow=slow.getNext();
if(fast==slow){
return true;
}
上面写的双向链表和循环链表的创建方法有点太繁琐，稍微修改了下：
双向链表的创建：
public static LinkNode creatDoubleLink(LinkNode root,LinkNode node){
if(root!=null&&biaoji<a.length-1){//如果根结点不为空，且还没达到数组的末尾
biaoji++;//使标记元素+1
node=new LinkNode(a[biaoji]);//得到根结点的下个结点
root.setNext(node);//将两者建立关系
node.setParent(root);
LinkNode node1=null;
creatDoubleLink(node,node1);//递归调用
}
return root;
}
单向循环链表的创建：
public static LinkNode createCircleLink(LinkNode node1){
if(biaoji!=sa.length-1&&root!=null){//如果还不是最后一个结点
biaoji++;
LinkNode node=new LinkNode(sa[biaoji]);
if(biaoji==sa.length-1){
nodee=node;//标记最后一个结点
}
node1.setNext(node);//建立结点之间的关系
createCircleLink(node);//递归调用
}
else{//如果是最后一个结点
nodee.setNext(root);//将最后一个结点的后继结点设为根结点
}
return root;
}
分享到：
相关推荐
链表是一种基础且重要的数据结构，它在计算机科学中扮演...同时，通过实际的编程练习，可以加深对链表理解，提高问题解决能力。总的来说，这是一个非常全面的链表学习资料包，对于数据结构课程设计的学生来说极具价值。
此外，链表倒置还可以作为面试中考察链表理解和操作能力的经典问题之一。 在链表倒置的基础上，可以进一步探讨双链表的倒置，以及如何优化倒置算法的时间复杂度和空间复杂度。例如，通过使用迭代而非递归，避免了...
在IT领域，数据结构是计算机科学的基础，它研究如何有效地组织和存储数据，以便于我们的程序可以...通过阅读和分析《数据结构》这本书中的相关内容，以及实践上述Java代码，你可以深化对链表理解，并提升你的编程技能。
这里，我们关注的是六道关于C++链表操作的题目，这些题目通常用于教学或面试中，帮助学生和求职者提升对链表理解和应用的能力。 一、链表的基本概念 链表不同于数组，它的元素不是在内存中连续存储的。每个链表节点...
适合人群：具备基础编程技能并熟悉C++语言的学习者和技术爱好者，尤其是正致力于提高对链表理解及应用水平的人士。 使用场景及目标：①理解链表与其他数据结构（特别是数组）间的区别；②熟练掌握链表的操作流程（如...
贪食蛇是一款经典的游戏，它的实现方式多样，其中一种是使用链表数据结构。链表是一种线性数据结构，由一系列节点（也...这是一种典型的将抽象数据结构应用于实际问题的示例，有助于加深对链表理解和编程技巧的提升。
1. 链表理解： 链表是一种动态数据结构，与数组不同，它不连续存储数据。每个节点包含两部分：数据元素和指向下一个节点的指针。链表提供了灵活的插入和删除操作，因为只需要改变相邻节点的指针即可。在这个图书...
链表是一种基础且重要的...通过“link”和“linked”这两个文件的学习，你可以深入理解单向链表和双向链表的差异，以及它们在实际问题中的应用。在实践中，不断练习这些操作，将有助于提高解决复杂数据结构问题的能力。
循环链表是一种特殊的链表结构，其特点在于链表的最后一个节点的指针域不再指向空，而是指向前一个节点，...通过理解这些链表结构的基本概念和操作方法，可以在实际的编程和应用开发中处理更复杂的数据关系和操作逻辑。
本篇将深入探讨单向动态链表的建立、修改及其核心操作，旨在帮助读者理解和掌握链表的基本原理和实现方法。 ### 单向链表的建立 单向链表，也称为单链表，其特点是每个节点只包含一个指向下一个节点的指针。在代码...
在C++编程中，链表是一种非常重要的数据结构，它不同于数组，不连续存储数据，而是通过节点间的指针关联来实现数据的存取。...通过阅读和理解这个源代码，可以加深对链表和C++对象导向编程的理解。
在本资料包中，“链表的实现 各种链表源码”提供了多种链表实现的源代码，帮助我们深入理解和应用链表。 1. **线性表与链表** 线性表是数据结构的基础，它是由相同类型元素构成的有限序列。链表是线性表的一种存储...
本题目的核心是利用链表的基本操作找到两个链表的交集，这是一个常见的算法问题，对于理解和掌握链表的操作具有很高的价值。 首先，我们需要了解链表的基本操作，包括创建链表、插入节点、删除节点和遍历链表。在...
双链表、循环链表和静态链表是数据结构中的三种不同类型的链式存储结构。它们各自有其特点和适用场景，下面我们将详细介绍这三种链表...理解和掌握这些链表类型及其操作，对于理解和编写高效的数据结构算法至关重要。
首先，让我们理解链表的基本概念。链表是由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素不需连续存储，这使得插入和删除操作更为灵活，只需改变相邻节点的指针即可...
首先，我们要理解链表的基本结构。一个链表节点通常包含两部分：数据域，存储元素值；指针域，指向下一个节点。在C语言中，我们可以定义一个结构体来表示链表节点： ```c typedef struct ListNode { int val; // ...
非常详细的链表构建过程，相信对于链表不怎么熟悉的人，会有很大帮助。
总的来说，要掌握链表操作，不仅需要理解链表的基本结构和指针的运作方式，还需要通过大量的编程实践来提升技巧，特别是在处理特殊边界条件和防止内存泄漏方面。对于复杂操作，可以采用分步骤、逐步构建的方法，确保...
总的来说，理解和掌握C语言中的双向链表和双向循环链表对于IT专业人士来说至关重要，无论是进行系统编程还是开发其他类型的软件。通过实践这些概念，你可以提升自己的编程技巧，并更好地应对各种复杂的数据处理需求...
在C语言中实现链表快速排序，首先需要理解链表和快速排序的基本概念。链表不同于数组，它不连续存储数据，而是通过指针连接各个节点。每个节点包含数据元素和指向下一个节点的指针。快速排序的核心是“分区操作”和...