【数据结构】线性表-循环链表（图解、c++、java）

文章目录

什么是循环链表？循环链表的存储方式（图解）循环链表的基本操作

1.初始化2.创建3.插入4.删除5.打印6.释放内存7.完整代码链表的优缺点总结

以下是本篇文章正文内容，下面案例可供参考。

什么是循环链表？

单链表中，只能向后，不能向前。
如果从当前节点开始，无法访问该节点前面的节点，而最后一个节点的指针指向头节点，形成一个环，就可以从任何一个位置出发，访问所有的节点，这就是循环链表。

循环链表和普通链表的区别就是最后一个节点的后继指针指向了头节点。

循环链表的存储方式（图解）

单向循环链表的最后一个节点的next域不能为空，而是指向头节点。

双向循环链表除了让最后一个节点的后继指针指向第一个节点外，还要让头节点的前驱指向最后一个节点。

循环链表的基本操作

因为循环链表的取值、查找代码没有改变，这里就不再写了。

首先定义一个结构体（内部类），包含数据域与指针域。

c++代码如下（示例）：

typedef struct LNode{
    int data;
    LNode *next;
}*linkList;

java代码如下（示例）：

public static class LNode{
 	int date;
	LNode next;
}

1.初始化

循环链表的初始化是指构建一个空表。先创建一个头节点，不存储数据，然后令其指针域指向自己。

单向循环链表

双向循环链表

c++代码如下（示例）：

bool Init(linkList &L){
    L = new LNode;
    if(!L){
        return false;
    }
    L->next = L;
    L->data = 0;
    return true;
}

java代码如下（示例）：

public static LNode init(LNode L){
	LNode lNode = new LNode();
    lNode.next = lNode;
    lNode.data = 0;
    return lNode;
}

2.创建

循环链表的创建过程与单链表，双链表相同。

我们以头插法为例。

c++代码如下（示例）：

void Create_H(linkList &L,int n){
    linkList s;
    while(n--){
        s = new LNode;
        cin>>s->date;
        //新节点next替换头节点next
        s->next = L->next;
        L->next = s;
    }
}

java代码如下（示例）：

public static void create_H(LNode L,int n){
    LNode s;
    Scanner sc = new Scanner(System.in);
        while(n-- > 0){
        s = new LNode();
        s.data = sc.nextInt();
        s.next = L.next;
        L.next = s;
    }
}

3.插入

插入也是相同的，只是在插入到最后一个节点时判断改一下。

c++代码如下（示例）：

bool Insert(linkList &L,int i,int e){
    linkList s,p = L;
    int j = 0;
    while(p->next!=L && jnext;
        j++;
    }
    if(j != i-1){
        return false;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

java代码如下（示例）：

public static boolean insert(LNode L,int i,int e){
    LNode s,p = L;
    int j = 0;
    while(p.next!=L && j 
4.删除 
删除也是相同的，只是在删除最后一个节点时判断改一下。 
 
c++代码如下（示例）： 
bool Delete(linkList &L,int i,int &e){
    linkList q,p = L;
    int j = 0;
    while(p->next!=L && jnext;
        j++;
    }
    if(j != i-1){
        return false;
    }
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return true;
}
 
java代码如下（示例）： 
public static int delete(LNode L,int i){
    LNode q,p = L;
    int j = 0;
    while(p.next!=L && j 
5.打印 
打印非常简单，直接上代码。 
c++代码如下（示例）： 
void Print(linkList L){
    linkList p = L->next;
    while(p != L){
        cout<data<<" ";
        p = p->next;
    }
    cout< 
java代码如下（示例）： 
public static void print(LNode L){
    LNode p = L.next;
    while(p!= L){
        System.out.print(p.data + " ");
        p = p.next;
    }
    System.out.println();
}
 
6.释放内存 
c++需要手动释放内存，而java不需要。 
c++代码如下（示例）： 
void Destroy(linkList &L){
    linkList tmp;
    for(linkList cur = L->next;cur!=NULL;){
        tmp = cur;
        cur = cur->next;
        delete tmp;
    }
    delete L;
}
 
7.完整代码 
c++代码如下（示例）： 
#include
using namespace std;

typedef struct LNode{
    int data;
    LNode *next;
}*linkList;

bool Init(linkList &L){
    L = new LNode;
    if(!L){
        return false;
    }
    L->next = L;
    L->data = 0;
    return true;
}

void Create_H(linkList &L,int n){
    linkList s;
    while(n--){
        s = new LNode;
        cin>>s->data;
        s->next = L->next;
        L->next = s;
    }
}

bool Insert(linkList &L,int i,int e){
    linkList s,p = L;
    int j = 0;
    while(p->next!=L && jnext;
        j++;
    }
    if(j != i-1){
        return false;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool Delete(linkList &L,int i,int &e){
    linkList q,p = L;
    int j = 0;
    while(p->next!=L && jnext;
        j++;
    }
    if(j != i-1){
        return false;
    }
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return true;
}

void Print(linkList L){
    linkList p = L->next;
    while(p != L){
        cout<data<<" ";
        p = p->next;
    }
    cout<next;cur!=L;){
        tmp = cur;
        cur = cur->next;
        delete tmp;
    }
    delete L;
}
int main(){
    linkList L;
    int choose=-1;
    int i,e,x,n;
    if(Init(L)){
        cout<<"初始化成功！"<>n;
    cout<<"依次输入要插入的元素"<>choose;
        switch (choose) {
            case 1:
                cout << "请输入要插入的位置和要插入的元素"<>i>>e;
                if(Insert(L,i,e)){
                    cout << "插入成功！"<>i;
                if(Delete(L,i,e)){
                    cout << "成功删除"< 
java代码如下（示例）： 
import java.util.Scanner;
public class E {

    public static class LNode{
        int data;
        LNode next;
    }

    public static LNode init(LNode L){
        LNode lNode = new LNode();
        lNode.next = lNode;
        lNode.data = 0;
        return lNode;
    }

    public static void create_H(LNode L,int n){
        LNode s;
        Scanner sc = new Scanner(System.in);
        while(n-- > 0){
            s = new LNode();
            s.data = sc.nextInt();
            s.next = L.next;
            L.next = s;
        }
    }

    public static boolean insert(LNode L,int i,int e){
        LNode s,p = L;
        int j = 0;
        while(p.next!=L && j 
 
链表的优缺点 
优点： 
链表是动态存储，不需要预先分配最大空间插入删除不需要移动元素 
缺点：
 每次动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个 int 的空间，因此存储密度低（数据所占空间 ÷ 节点所占总空间） 
 
总结 
双向循环链表和单向循环链表的改发基本相同，所以只发了单向循环链表的代码。 
没想着偷懒，只是想着多出的时间赶紧复习下面的内容！！ 
通过观察我写的循环链表代码，总感觉和单链表没什么区别，循环查找好像没有什么用。其实用处还是蛮大的，只是受限于我的操作要求看起来没什么变化，在做相关题目的时候会发现，区别还是很大的。（废话） 
下期预告：栈链

【数据结构】线性表-循环链表（图解、c++、java）

Java相关栏目本月热门文章