链表的操作与实现（Java C）

sonnet_14_82

883人浏览 · 2026-01-10 03:08:12

sonnet_14_82 · 2026-01-10 03:08:12 发布

02_链表

对于顺序表而言，内存利用率很高，按位置查找效率高。但插入删除需要搬移大量元素，时间效率低。并且堆区必须出现连续的空间，空间不满足。因此可以考虑链表

链表的定义：

在物理上不连续，在逻辑上连续，大小不固定
物理上必须牺牲空间性，增加指针域，指向逻辑连续的下一个元素
链式存储关心的是节点结构，顺式存储关心的是整体结构
- 数据域：存储元素的区域
- 指针域：存储直接后继位置的区域（也叫next域）

数据域	指针域

1. 单向链表

单向链表只能往一个方向访问，一旦访问了下一个节点，那么再也不能回到之前的状态了

1.1 单向链表的申明

需要申明节点和表头，每个节点的next域指向下一个节点，而表头则存储头节点和节点的总个数等，在头节点（head）中的value无任何意义，next则是指向第一个节点。

C实现：

typedef int Element;

//节点的申明
typedef struct node {
	Element value;
	struct node* next;
}node_t;

//表头的申明
typedef struct {
	node_t head;
	int count;
}LinkList_t;

Java 实现：

public class Element {

    int value;

    public Element(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (this.getClass() != obj.getClass())
            return false;
        Element other = (Element)obj;
        return this.value == other.value;
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }
}

public class LinkListTable {

    //节点结构
    private static class Node {
        Element value;
        Node next;

        public Node(Element value) {
            this.value = value;
            this.next = null;
        }

        public Node(Element value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(){}
    }

    int count;
    Node head;

    public LinkListTable() {
        this.head = new Node();
        this.head.next = null;
        this.count = 0;
    }
}

1.2 创建链表

Java中直接new即可

c需要通过malloc函数来创建一个表头，如果创建成功就对这个链表进行初始化

C 实现：

LinkList_t* createLinkList() {
	//创建表头
	LinkList_t* link_table = malloc(sizeof(LinkList_t));
	//判断是否创建成功
	if (link_table == NULL) {
		printf("link_table malloc failed\n");
	}

	//初始化
	link_table->count = 0;
	link_table->head.next = NULL;
	link_table->head.value = 0;

	return link_table;
}

1.3 头插

创建辅助指针p指向头节点，这个p就是需要添加元素的前驱节点。创建新的节点，处理新创建的节点，将新节点的value进行赋值，让新节点指向head.next。然后处理老节点，让头节点的next指向新节点，即head.next = new_node。

C 实现：

int insertLinkListHead(LinkList_t* link_table, Element value) {
	//判断链表是否存在
	if (link_table == NULL) return -1;
	//p就是添加元素的前驱
	node_t* p = &link_table->head;
	//创建新节点
	node_t* new_node = malloc(sizeof(node_t));
	if (new_node == NULL) return -1;
	//头插
	new_node->value = value;
	new_node->next = p->next;
	p->next = new_node;
	link_table->count++;

	return 0;
}

Java 实现:

    /*
        功能： 头插
        参数： 需要插入的元素
        返回值： 成功true 失败false
     */
    public boolean insertLinkListHead(Element value) {
        if (value == null) return false;
        //p为前驱节点
        Node p = this.head;
        //创建新节点
        Node newNode = new Node(value, p.next);
        //处理老节点
        p.next = newNode;
        this.count++;

        return true;
    }

1.4 任意位置插入

先判断需要插入位置的索引合不合法，因为要插入元素，所以必须先找到该索引的前驱节点。创建指针p指向头节点，当计数器和需要的索引 - 1相等时， p就指向了前驱节点。然后创建新节点并处理，在处理前驱节点，最后链表节点数 + 1。

C 实现:

int insertLinkListPos(LinkList_t* link_table, int pos, Element value) {
	//索引合法性
	if (pos < 0 || pos > link_table->count) {
		printf("pos is invalid\n");
		return -1;
	}
	int index = 0;
	node_t* p = &link_table->head;
	//当index == pos - 1时，p为前驱节点
	while (p && index <= pos - 1) {
		p = p->next;
		index++;
	}
	if (p == NULL) return -1;
	//创建新节点
	node_t* new_node = malloc(sizeof(node_t));
	if (new_node == NULL) {
		printf("new_node malloc failed\n");
		return -1;
	}
	//插入
	new_node->value = value;
	new_node->next = p->next;
	p->next = new_node;
	link_table->count++;

	return 0;
}

Java 实现：

    /*
        功能： 任意位置插入元素
        参数： 需要插入的索引
        返回值： 成功true 失败false
     */
    public boolean insertLinkListPos(int pos, Element value) {
        //索引合法性
        if (pos < 0 || pos > this.count) {
            System.out.println("not found index");
            return false;
        }
        //寻找前驱节点
        int index = 0;
        Node p = this.head;
        while (p != null && index != pos -1) {
            p = p.next;
            index++;
        }
        if (p == null) return false;
        //插入
        Node newNode = new Node(value, p.next);
        p.next = newNode;
        this.count++;

        return true;
    }

1.5 打印链表中的元素

定义一个辅助指针，指向表头，让辅助指针不断后移，当指向空时，代表链表为空

C 实现：

void showLinkList(const LinkList_t* link_table) {
	printf("LinkList have %d node\n", link_table->count);
	//创建辅助指针
	node_t* p = link_table->head.next;
	while (p) {
		printf("%d\t", p->value);
		//指针后移
		p = p->next;
	}
	printf("\n");
}

Java 实现：

    /*
        功能： 打印链表中的元素
        参数： 无
        返回值： 无
     */
    public void showLinkList() {
        System.out.println("LinkList have " + this.count + " node");
        //辅助指针p
        Node p = this.head.next;
        while (p != null) {
            System.out.print(p.value + " ");
            p = p.next;
        }
        System.out.println();
    }

如果是Elenment对象需要重写toString

1.6 删去链表中的元素

因为要删去元素，所以必须先找到该元素的前驱节点，因此定义一个辅助指针，不断指向前驱节点。当找到该元素的前驱节点时，定义一个临时指针来指向该元素的节点（便于free）。然后处理前驱节点，让前驱节点的next域指向临时指针的下一个节点，最后free临时指针，让链表的节点数 - 1。

C 实现:

int deleteLinkListElement(LinkList_t* link_table, Element value) {
	//辅助指针指向value的前驱节点
	node_t* p = &link_table->head;
	//寻找value
	while (p->next && p->next->value != value) {
		p = p->next;
	}
	//如果没找到value
	if (p->next == NULL) {
		printf("not found value\n");
		return -1;
	}
	//删除
	node_t* tmp = p->next;
	p->next = tmp->next;
	free(tmp);

	link_table->count--;
	
	return 0;
}

Java 实现：

    /*
        功能： 删去链表中的元素
        参数： 需要删去的元素
        返回值： 成功true 失败false
     */
    public boolean deleteLinkListElement(Element value) {
        //创建前驱指针p
        Node p = this.head;
        //寻找value
        //重写equals方法
        while(p.next != null && !p.next.value.equals(value)) {
            p = p.next;
        }
        //没找到value
        if (p.next == null) {
            System.out.println("not found value");
            return false;
        }
        //删除
        Node tmp = p.next;
        p.next = tmp.next;
        //清理
        tmp.next = null;
        tmp.value = null;
        this.count--;

        return true;
    }

在比较两个Element类的时候需要重写equals和hashCode方法

1.7 释放链表

从前往后不断释放节点，创建指针p指向前驱节点，在创建临时指针来指向需要释放的节点。让p指向临时指针的下一个节点，然后释放临时指针，最后释放表头。

C 实现：

void releaseLinkList(LinkList_t* link_table) {
	if (link_table) {
		//创建指针p指向前驱节点
		node_t* p = &link_table->head;
		//临时指针
		node_t* tmp;
		while (p->next) {
			tmp = p->next;
			p->next = tmp->next;
			free(tmp);
			link_table->count--;
		}
		printf("LinkTable have %d node\n", link_table->count);
		//释放表头
		free(link_table);
	}
}

Java 实现：

    /*
        功能： 释放链表
        参数： 无
        返回值： 无
     */
    public void releaseLinkList() {
        //创建前置指针
        Node p = this.head;
        //创建临时指针
        Node tmp;
        while (p.next != null) {
            tmp = p.next;
            p.next = tmp.next;
            tmp.next = null;
            tmp.value = null;
            this.count--;
        }
        System.out.println("LinkList have " + this.count + " node");
        //释放表头
        this.head.value = null;
        this.head.next = null;
        this.count = 0;
    }

1.8 完整实现

C 实现：

LinkList.h:

#pragma once

typedef int Element_t;

// 链式存储， 定义节点结构
typedef struct _node{
	Element_t value;
	struct _node* next;
}node_t;

//定义链表表头结构
typedef struct {
	node_t head;
	int count;
}LinkList_t;

LinkList_t* createLinkList();
void releaseLinkList(LinkList_t* link_table);

int insertLinkListHeader(LinkList_t* link_table, Element_t value);
int insertLinkListPos(LinkList_t* link_table, int pos, Element_t value);

int deleteLinkListElement(LinkList_t* link_table, Element_t value);

void showLinkList(const LinkList_t* list_table);

LinkList.c:

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

/*
	功能： 创建链表表头
	参数： 无
	返回值： 创建之后的链表表头
		1. 创建链表表头
		2. 初始化
*/
LinkList_t* createLinkList() {
	//创建
	LinkList_t* table = NULL;
	table = malloc(sizeof(LinkList_t));
	if (table == NULL) {
		printf("table malloc failed\n");
		return NULL;
	}
	//初始化
	table->count = 0;
	table->head.value = 0;
	table->head.next = NULL;

	return table;
}

/*
	功能： 头插法
	参数： 需要插入的链表 要插入的元素
	返回值： 成功0 失败-1
		1. 创建一个临时指针来指向表头
		2. 创建新节点
		3. 处理新节点
		4. 处理老节点
*/
int insertLinkListHeader(LinkList_t* link_table, Element_t value) {
	// 创建一个辅助指针指向表头
	// p就是要添加元素的前驱
	node_t* p = &link_table->head;
	//创建新节点
	node_t* new_node = malloc(sizeof(node_t));
	if (new_node == NULL) return -1;
	// 处理新节点
	new_node->value = value;
	new_node->next = p->next;
	// 处理老节点
	p->next = new_node;

	link_table->count++;

	return 0;
}

/*
	功能： 打印链表中的信息
	参数： 需要操作的链表
	返回值： 无
		1. 遍历
*/
void showLinkList(const LinkList_t* link_table) {
	//创建辅助指针
	node_t* p = link_table->head.next;
	//当辅助指针为空，则停止
	printf("LinkList count is %d\n", link_table->count);
	while (p) {
		printf("%d\t", p->value);
		//辅助指针后移
		p = p->next;
	}
	printf("\n");
}

/*
	功能:  删除元素
	参数： 需要删除元素的链表 需要删除的元素
	返回值： 0成功 -1失败
		1. 
*/
int deleteLinkListElement(LinkList_t* link_table, Element_t value) {
	//辅助指针指向value的前驱节点
	node_t* p = &link_table->head;
	while (p->next) {
		if (p->next->value == value) {
			break;
		}
		p = p->next;
	}
	if (p->next == NULL) {
		printf("not found value\n");
		return -1;
	}
	//删除
	node_t* tmp = p->next;
	p->next = tmp->next;
	free(tmp);

	link_table->count--;

	return 0;
}

/*
	功能： 在任意位置插入元素
	参数： 需要插入元素的链表 需要插入的位置索引pos 需要插入的元素
	返回值： 成功0 失败-1
		1. 找到pos - 1索引的节点首地址
		2. 创建新节点，并处理新节点
		3. 处理老节点
*/
int insertLinkListPos(LinkList_t* link_table, int pos, Element_t value) {
	if (pos < 0 || pos > link_table->count) {
		printf("insert pos invalid\n");
		return -1;
	}
	//找到pos - 1索引节点的首地址
	node_t* p = &link_table->head;
	int index = 0;
	while (p && index < pos - 1) {
		p = p->next;
		index++;
	}
	if (p == NULL) {
		return -1;
	}
	node_t* new_node = malloc(sizeof(node_t));
	if (new_node == NULL) {
		printf("new_node malloc failed\n");
		return -1;
	}
	new_node->value = value;
	new_node->next = p->next;
	p->next = new_node;
	link_table->count++;

	return 0;
}

/*
	功能： 释放链表
	参数： 需要释放的链表
	返回值： 无
		1. 守住头节点， 一直删除头节点后面的元素
		2. 定义指针p指向头节点
		3. 定义临时指针tmp存储p->next
		4. 处理p的next，释放tmp
		5. 释放表头
*/
void releaseLinkList(LinkList_t* link_table) {
	if (link_table) {
		node_t* p = &link_table->head;
		node_t* tmp;
		while (p->next) {
		tmp = p->next;
		p->next = tmp->next;
		free(tmp);
		link_table->count--;
		}
		printf("LinkTable have %d node\n", link_table->count);
		free(link_table);
	}
}

main.c:

#include<stdio.h>
#include<stdlib.h>
#include "LinkList.h"

void test01() {
	LinkList_t* link_table = createLinkList();
	if (link_table == NULL) 
		return;
	for (int i = 0; i < 10; i++) {
		insertLinkListHeader(link_table, 100 + i);
	}

	showLinkList(link_table);
	printf("----------------\n");
	insertLinkListPos(link_table, 0, 82);
	showLinkList(link_table);
	printf("-----------------\n");
	deleteLinkListElement(link_table, 109);
	deleteLinkListElement(link_table, 104);
	showLinkList(link_table);
	printf("-----------------\n");
	releaseLinkList(link_table);
	
}

int main() {
	test01();

	return 0;
}

Java 实现：

Element类：

package com.Sonnet.LinkList;

public class Element {

    int value;

    public Element(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (this.getClass() != obj.getClass())
            return false;
        Element other = (Element)obj;
        return this.value == other.value;
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }
}

LinkListTable类：

package com.Sonnet.LinkList;

public class LinkListTable {

    //节点结构
    private static class Node {
        Element value;
        Node next;

        public Node(Element value) {
            this.value = value;
            this.next = null;
        }

        public Node(Element value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(){}
    }

    int count;
    Node head;

    public LinkListTable() {
        this.head = new Node();
        this.head.next = null;
        this.count = 0;
    }


    /*
        功能： 头插
        参数： 需要插入的元素
        返回值： 成功true 失败false
     */
    public boolean insertLinkListHead(Element value) {
        if (value == null) return false;
        //p为前驱节点
        Node p = this.head;
        //创建新节点
        Node newNode = new Node(value, p.next);
        //处理老节点
        p.next = newNode;
        this.count++;

        return true;
    }

    /*
        功能： 打印链表中的元素
        参数： 无
        返回值： 无
     */
    public void showLinkList() {
        System.out.println("LinkList have " + this.count + " node");
        //辅助指针p
        Node p = this.head.next;
        while (p != null) {
            System.out.print(p.value + " ");
            p = p.next;
        }
        System.out.println();
    }

    /*
        功能： 删去链表中的元素
        参数： 需要删去的元素
        返回值： 成功true 失败false
     */
    public boolean deleteLinkListElement(Element value) {
        //创建前驱指针p
        Node p = this.head;
        //寻找value
        //重写equals方法
        while(p.next != null && !p.next.value.equals(value)) {
            p = p.next;
        }
        //没找到value
        if (p.next == null) {
            System.out.println("not found value");
            return false;
        }
        //删除
        Node tmp = p.next;
        p.next = tmp.next;
        //清理
        tmp.next = null;
        tmp.value = null;
        this.count--;

        return true;
    }

    /*
        功能： 任意位置插入元素
        参数： 需要插入的索引
        返回值： 成功true 失败false
     */
    public boolean insertLinkListPos(int pos, Element value) {
        //索引合法性
        if (pos < 0 || pos > this.count) {
            System.out.println("not found index");
            return false;
        }
        //寻找前驱节点
        int index = 0;
        Node p = this.head;
        while (p != null && index != pos -1) {
            p = p.next;
            index++;
        }
        if (p == null) return false;
        //插入
        Node newNode = new Node(value, p.next);
        p.next = newNode;
        this.count++;

        return true;
    }

    /*
        功能： 释放链表
        参数： 无
        返回值： 无
     */
    public void releaseLinkList() {
        //创建前置指针
        Node p = this.head;
        //创建临时指针
        Node tmp;
        while (p.next != null) {
            tmp = p.next;
            p.next = tmp.next;
            tmp.next = null;
            tmp.value = null;
            this.count--;
        }
        System.out.println("LinkList have " + this.count + " node");
        //释放表头
        this.head.value = null;
        this.head.next = null;
        this.count = 0;
    }
}

test类：

package com.Sonnet.LinkList;

public class test {
    public static void main(String[] args) {
        test01();
    }

    public static void test01() {
        LinkListTable link_table = new LinkListTable();
        for (int i = 0; i < 10; i++) {
            link_table.insertLinkListHead(new Element(100 + i));
        }
        link_table.showLinkList();
        System.out.println("---------------");
        link_table.deleteLinkListElement(new Element(109));
        link_table.deleteLinkListElement(new Element(100));
        link_table.showLinkList();
        System.out.println("-----------------");
    }
}

2. 单向循环链表

单向循环链表的最后节点的next域不在指向空，而是指向头节点

2.1 约瑟夫环

在犹太罗马战争期间，41名犹太士兵被罗马军队包围。为了不被俘虏，他们决定集体自杀。他们围成一个圈，从第一个人开始报数，每数到第3个人就让他自杀，直到剩下最后一个人，由他投降。约瑟夫不想死，他应该站在哪个位置？

C 实现：

Joseph.h:

#pragma once

//节点
typedef struct node {
	int number;
	struct node* next;
}node_t;

//约瑟夫环
typedef struct {
	node_t* head;
	node_t* tail;
}Joseph_t;

/*初始化*/
void initJoseph(Joseph_t* game, int count);

/*遍历打印*/
void showJoseph(const Joseph_t* game);

/*开始约瑟夫环游戏*/
void startJoseph(Joseph_t* game, int kill);

Joseph.c:

#include <stdio.h>
#include <stdlib.h>
#include "Joseph.h"

void initJoseph(Joseph_t* game, int number) {
	//创建节点
	for (int i = 1; i <= number; i++) {
		node_t* node = malloc(sizeof(node_t));
		if (node == NULL) return;
		node->number = i;
		//第一个节点
		if (game->head == NULL) {
			game->head = node;
			game->tail = node;
		}
		//添加节点
		else {
			game->tail->next = node;
			game->tail = node;
		}
		game->tail->next = game->head;
	}
}

void showJoseph(const Joseph_t* game) {
	node_t* p = game->head;
	do {
		printf("%d ", p->number);
		p = p->next;
	} while (p != game->head);
	printf("\n");
}

void startJoseph(Joseph_t* game, int kill) {
	//指向需要杀的人
	node_t* cur = game->head;
	//辅助指针，指向前驱
	node_t* pre = game->tail;
	//遍历， 直到只剩下一个人
	while (cur->next != cur) {
		//报数
		for (int i = 1; i < kill; i++) {
			pre = cur;
			cur = cur->next;
		}
		//杀人
		pre->next = cur->next;
		free(cur);
		//cur指针后移
		cur = pre->next;
	}
	printf("win is %d\n", cur->number);
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include "Joseph.h"

void test(void) {
	Joseph_t game = { NULL, NULL };
	initJoseph(&game, 41);
	showJoseph(&game);
	startJoseph(&game, 3);
}

int main() {
	test();

	return 0;
}

Java 实现:

Joseph:

package com.Sonnet.Joseph;

public class Joseph {

    //节点结构
    static class Node {
        int val;
        Node next;

        public Node() {};
        public Node(int val) {
            this.val = val;
        }
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    Node head;
    Node tail;

    public Joseph(int number){
        for (int i = 1; i <= number; i++) {
            Node node = new Node(i);
            if (head == null) {
                this.head = node;
                this.tail = node;
            }
            else {
                this.tail.next = node;
                this.tail = node;
            }
            this.tail.next = head;
        }
    }

    public void showJoseph() {
        Node p = this.head;
        do {
            System.out.print(p.val + " ");
            p = p.next;
        } while (p != head);
        System.out.println();
    }

    public void startJoseph(int kill) {
        Node cur = this.head;
        Node pre = this.tail;
        //仅剩一人存活
        while (cur.next != cur) {
            //报数
            for (int i = 1; i < kill; i++) {
                pre = cur;
                cur = cur.next;
            }
            pre.next = cur.next;
            cur.next = null;
            cur = pre.next;
        }
        System.out.println(cur.val + " is winner");
    }

}

test:

package com.Sonnet.Joseph;

public class Test {
    public static void main(String[] args) {
        testJoseph();
    }

    public static void testJoseph() {
        Joseph joseph = new Joseph(41);
        joseph.showJoseph();
        joseph.startJoseph(3);
    }
}

3. 双向链表

双链表的节点包含两个指针域，next域和prior域，一个指向后继节点，一个指向前驱节点

prior	data	next

4. 双向循环链表

将单向循环链表和双向链表相结合

4.1 申明

双向循环链表存在一个数据域，一个next域来指向后继节点，一个prev域来指向前驱节点，同时还存在一个头节点

C 实现：

typedef int Element_t;

//DNode为节点结构
//DLinkHeader为头节点结构
typedef struct d_node {
	int val;
	struct d_node* next;
	struct d_node* prev;
}DNode_t, DLinkHeader_t;

Java 实现：

Element:

package com.Sonnet.doubleLoopLink;

public class Element {
    int val;

    public Element() {}

    public Element(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return String.valueOf(this.val);
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(this.val);
    }

    @Override
    public boolean equals(Object obj) {
        //地址相同直接返回true
        if (this == obj)
            return true;
        //类型不同返回false
        if (this.getClass() != obj) {
            return false;
        }
        //一旦类型相等就可以进行强换
        Element other = (Element)obj;
        return other.val == other.val;
    }
}

DLink:

public class DLink {

    //节点结构申明
    private static class DNode {
        Element val;
        DNode next;
        DNode prev;

        public DNode() {}
        public DNode(Element val) {
            this.val = val;
        }
    }

    //头节点，不需要记录数据
    DNode head;
}

4.2 初始化

由用户自己维护双向循环链表，C中只需要对传入的头节点进行初始化即可，Java中通过构造方法即可实现。让前驱和后继都指向自己

C 实现：

/*初始化*/
void initDLink(DLinkHeader_t* header) {
	header->next = header;
	header->prev = header;
}

Java 实现：

    public DLink() {
        this.head = new DNode();
        this.head.next = this.head;
        this.head.prev = this.head;
    }

4.3 插入

对于插入操作，其核心就是创建一个新的节点，然后让新节点的next域指向后继，prev域指向前驱，前驱的next指向新节点，后继的prev域指向新节点即可因此可以设计一个内部方法来实现核心插入操作，从而简化代码。

C 实现：

/*
	功能： 插入
	参数： 前驱节点 新节点 后继节点
	返回值： 无
*/
static void addDNode(DNode_t* prev, DNode_t* new_node, DNode_t* next) {
	next->prev = new_node;
	new_node->next = next;
	new_node->prev = prev;
	prev->next = new_node;
}

Java 实现：

    /*
        功能： 插入
        参数： 前驱节点 需要插入的节点 后继节点
        返回值： 无
     */
    private void addDNode(DNode prev, DNode newDNode, DNode next) {
        next.prev = newDNode;
        newDNode.next = next;
        newDNode.prev = prev;
        prev.next = newDNode;
    }

4.3.1 头插

C 实现：

/*头插*/
void insertDLinkHeader(DLinkHeader_t* header, Element_t val) {
	//创建节点
	DNode_t* new_node = malloc(sizeof(DNode_t));
	if (new_node == NULL) return;
	new_node->val = val;
	//插入
	addDNode(header, new_node, header->next);
}

Java 实现:

    /*
        功能： 头插
        参数： 需要插入的元素
        返回值: 无
     */
    public void insertDLinkHeader(Element val) {
        //创建节点
        DNode newDNode = new DNode(val);
        //插入
        addDNode(this.head, newDNode, this.head.next);
    }

4.3.2 尾插

C 实现：

/*尾插*/
void insertDLinkRear(DLinkHeader_t* header, Element_t val) {
	//创建节点
	DNode_t* new_node = malloc(sizeof(DNode_t));
	if (new_node == NULL) return;
	new_node->val = val;
	//插入
	addDNode(header->prev, new_node, header);
}

Java 实现：

    /*
        功能： 尾插
        参数： 需要插入的元素
        返回值： 无
     */
    public void insertDLinkRear(Element val) {
        //创建节点
        DNode newDNode = new DNode(val);
        //插入
        addDNode(this.head.prev, newDNode, this.head);
    }

4.4 遍历打印

用辅助指针p指向第一个节点，让不断遍历打印，直到p指向头节点

C 实现：

/*遍历打印*/
void showDLink(const DLinkHeader_t* header) {
	//创建辅助指针p
	DNode_t* p = header->next;
	int cnt = 0;
	while (p != header) {
		printf("%d\t", p->val);
		p = p->next;
		cnt++;
	}
	printf("\nthis link have %d node\n", cnt);
}

Java 实现：

    /*
        功能： 遍历打印
        参数： 无
        返回值： 无
     */
    void showDLink() {
        DNode p = this.head.next;
        int cnt = 0;
        while (p != this.head) {
            System.out.print(p.val + " ");
            p = p.next;
            cnt++;
        }
        System.out.println();
        System.out.println("link have " + cnt + "node");
    }

4.5 删除

删除的核心是将需要删除的元素的前驱的后继指向后继，将后继的前驱指向后继。因此也可以通过内部方法来实现核心逻辑。

C 实现：

/*
	功能： 删除
	参数： 前驱节点 后继节点
	返回值： 无
*/
static deleteDNode(DNode_t* prev, DNode_t* next) {
	prev->next = next;
	next->prev = prev;
}

Java 实现：

    /*
        功能： 删除
        参数： 前驱节点 后继节点
        返回值： 无
     */
    private void deleteDNode(DNode prev, DNode next) {
        prev.next = next;
        next.prev = prev;
    }

4.5.1 删除单个元素

C 实现：

/*删除单个元素*/
void deleteDLinkElement(DLinkHeader_t* header, Element_t val) {
	//辅助指针p
	DNode_t* p = header->next;
	//查找
	while (p != header && p->val != val) {
		p = p->next;
	}
	//查找失败
	if (p == header) {
		printf("not found value\n");
		return;
	}
	//删除
	deleteDNode(p->prev, p->next);
	free(p);
}

Java 实现：

    /*
        功能： 删除单个元素
        参数： 需要删除的元素
        返回值： 无
     */
    public void deleteDLinkElement(Element val) {
        //辅助指针p
        DNode p = this.head.next;
        //查找
        while (p != this.head && p.equals(val)) {
            p = p.next;
        }
        //查找失败
        if (p == this.head) {
            System.out.println("not found value");
            return;
        }
        //删除
        deleteDNode(p.prev, p.next);
        p.next = null;
        p.prev = null;
        p.val = null;
    }

4.5.2 删除全部元素

C 实现：

/*删除全部元素*/
void deleteALLDLink(DLinkHeader_t* header) {
	//辅助指针
	DNode_t* p = header->next;
	while (p != header) {
		deleteDNode(header, p->next);
		free(p);
		p = header->next;
	}
}

Java 实现：

    /*
        功能： 删除全部元素
        参数： 无
        返回值： 无
     */
    public void deleteALLDLink() {
        //辅助指针p
        DNode p = this.head.next;
        while (p != this.head) {
            deleteDNode(this.head, p.next);
            p.next = null;
            p.val = null;
            p.prev = null;
            p = this.head.next;
        }
    }

4.6 完整实现

C 实现：

doubleLoopLink.h:

#pragma once

typedef int Element_t;

typedef struct d_node{
	Element_t val;
	struct d_node* next;
	struct d_node* prev;
} DNode_t, DLinkHeader_t;

/*
	功能： 初始化链表
	参数： 需要初始化的链表表头
	返回值： 无
		双向循环链表的头建议是用户自己维护，表头放在栈上，放在全局变量
*/
void initDLink(DLinkHeader_t* header);

/*
	功能： 头插
	参数： 需要插入元素的链表 需要插入的元素
	返回值： 无
*/
void insertDLinkHeader(DLinkHeader_t* header, Element_t val);

/*
	功能： 尾插
	参数： 需要插入元素的链表 需要插入的元素
	返回值： 无
*/
void insertDLinkRear(DLinkHeader_t* header, Element_t val);

/*
	功能： 打印双向循环链表中的信息
	参数： 需要操作的链表
	返回值： 无
*/
void showDLink(const DLinkHeader_t* header);

/*
	功能： 删除链表中的元素
	参数： 需要删除元素的链表 需要删除的元素
	返回值： 无
*/
void deleteDLinkElement(DLinkHeader_t* header, Element_t val);

/*
	功能： 删除所有元素
	参数： 需要删除元素的链表
	返回值： 无
*/
void deleteALLDLink(DLinkHeader_t* header);

doublieLoopLink.c:

#include <stdio.h>
#include <stdlib.h>
#include "doubleLoopList.h"

/*初始化*/
void initDLink(DLinkHeader_t* header) {
	header->next = header;
	header->prev = header;
	header->val = 0;
}

/*
	功能： 插入节点
	参数： 前驱节点 新节点 后继节点
	返回值： 无
*/
static void addNode(DNode_t* prev, DNode_t* new_node, DNode_t* next) {
	next->prev = new_node;
	new_node->next = next;
	new_node->prev = prev;
	prev->next = new_node;
}

/*头插*/
void insertDLinkHeader(DLinkHeader_t* header, Element_t val) {
	//创建新节点
	DNode_t* new_node = malloc(sizeof(DNode_t));
	if (new_node == NULL) return;
	new_node->val = val;
	//插入
	addNode(header, new_node, header->next);
}

/*尾插*/
void insertDLinkRear(DLinkHeader_t* header, Element_t val) {
	//创建新节点
	DNode_t* new_node = malloc(sizeof(DNode_t));
	if (new_node == NULL) return;
	new_node->val = val;
	//插入
	addNode(header->prev, new_node, header);
}

/*遍历打印*/
void showDLink(const DLinkHeader_t* header) {
	DNode_t* pos = header->next;
	int cnt = 0;
	while (pos != header) {
		printf("%d\t", pos->val);
		cnt++;
		pos = pos->next;
	}
	printf("\nthis DLink have %d node\n", cnt);
}

/*
	功能： 删除节点
	参数： 前驱节点 后继节点
	返回值： 无
*/
static delteDNode(DNode_t* prev, DNode_t* next) {
	prev->next = next;
	next->prev = prev;
}

/*删除元素*/
void deleteDLinkElement(DLinkHeader_t* header, Element_t val) {
	//辅助指针
	DNode_t* pos = header->next;
	//查找元素
	while (pos != header && pos->val != val) {
		pos = pos->next;
	}
	//查找失败
	if (pos == header) {
		printf("not found value\n");
		return;
	}
	//删除
	delteDNode(pos->prev, pos->next);
	free(pos);
}

/*删除所有元素*/
void deleteALLDLink(DLinkHeader_t* header) {
	//辅助指针
	DNode_t* pos = header->next;
	while (pos != header) {
		delteDNode(pos->prev, pos->next);
		free(pos);
		pos = header->next;
	}
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include "doubleLoopList.h"

DLinkHeader_t head;

void test01(void) {
	initDLink(&head);
	for (int i = 0; i < 5; i++) {
		insertDLinkHeader(&head, 100 + i);
		insertDLinkRear(&head, 50 + i);
	}
	showDLink(&head);
	printf("---------------\n");
	deleteDLinkElement(&head, 50);
	deleteDLinkElement(&head, 104);
	showDLink(&head);
	printf("--------------\n");
	deleteALLDLink(&head);
	showDLink(&head);
}

int main() {
	test01();

	return 0;
}

Java 实现：

Element:

package com.Sonnet.doubleLoopLink;

public class Element {
    int val;

    public Element() {}

    public Element(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return String.valueOf(this.val);
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(this.val);
    }

    @Override
    public boolean equals(Object obj) {
        //地址相同直接返回true
        if (this == obj)
            return true;
        //类型不同返回false
        if (this.getClass() != obj) {
            return false;
        }
        //一旦类型相等就可以进行强换
        Element other = (Element)obj;
        return other.val == other.val;
    }
}

DLink:

package com.Sonnet.doubleLoopLink;

public class DLink {

    //节点结构申明
    private static class DNode {
        Element val;
        DNode next;
        DNode prev;

        public DNode() {}
        public DNode(Element val) {
            this.val = val;
        }
    }

    //头节点，不需要记录数据
    DNode head;

    public DLink() {
        this.head = new DNode();
        this.head.next = this.head;
        this.head.prev = this.head;
    }

    /*
        功能： 插入
        参数： 前驱节点 需要插入的节点 后继节点
        返回值： 无
     */
    private void addDNode(DNode prev, DNode newDNode, DNode next) {
        next.prev = newDNode;
        newDNode.next = next;
        newDNode.prev = prev;
        prev.next = newDNode;
    }

    /*
        功能： 头插
        参数： 需要插入的元素
        返回值: 无
     */
    public void insertDLinkHeader(Element val) {
        //创建节点
        DNode newDNode = new DNode(val);
        //插入
        addDNode(this.head, newDNode, this.head.next);
    }

    /*
        功能： 尾插
        参数： 需要插入的元素
        返回值： 无
     */
    public void insertDLinkRear(Element val) {
        //创建节点
        DNode newDNode = new DNode(val);
        //插入
        addDNode(this.head.prev, newDNode, this.head);
    }

    /*
        功能： 遍历打印
        参数： 无
        返回值： 无
     */
    void showDLink() {
        DNode p = this.head.next;
        int cnt = 0;
        while (p != this.head) {
            System.out.print(p.val + " ");
            p = p.next;
            cnt++;
        }
        System.out.println();
        System.out.println("link have " + cnt + " node");
    }

    /*
        功能： 删除
        参数： 前驱节点 后继节点
        返回值： 无
     */
    private void deleteDNode(DNode prev, DNode next) {
        prev.next = next;
        next.prev = prev;
    }

    /*
        功能： 删除单个元素
        参数： 需要删除的元素
        返回值： 无
     */
    public void deleteDLinkElement(Element val) {
        //辅助指针p
        DNode p = this.head.next;
        //查找
        while (p != this.head && p.equals(val)) {
            p = p.next;
        }
        //查找失败
        if (p == this.head) {
            System.out.println("not found value");
            return;
        }
        //删除
        deleteDNode(p.prev, p.next);
        p.next = null;
        p.prev = null;
        p.val = null;
    }

    /*
        功能： 删除全部元素
        参数： 无
        返回值： 无
     */
    public void deleteALLDLink() {
        //辅助指针p
        DNode p = this.head.next;
        while (p != this.head) {
            deleteDNode(this.head, p.next);
            p.next = null;
            p.val = null;
            p.prev = null;
            p = this.head.next;
        }
    }
}

Test:

package com.Sonnet.doubleLoopLink;

public class Test {
    public static void main(String[] args) {
        testDoubleLoopLink();
    }

    public static void testDoubleLoopLink() {
        DLink dLink = new DLink();
        for (int i = 0; i < 5; i++) {
            dLink.insertDLinkHeader(new Element(i + 100));
            dLink.insertDLinkRear(new Element(i + 50));
        }
        dLink.showDLink();
        System.out.println("---------------");
        dLink.deleteDLinkElement(new Element(50));
        dLink.deleteDLinkElement(new Element(104));
        dLink.showDLink();
        System.out.println("---------------");
        dLink.deleteALLDLink();
        dLink.showDLink();
    }
}