链表数据结构
万次阅读
2019-02-17 22:57:14
欢迎大家关注我的公众号【老周聊架构】，Java后端主流技术栈的原理、源码分析、架构以及各种互联网高并发、高性能、高可用的解决方案。

两种数据结构都是线性表，在排序和查找等算法中都有广泛的应用

一、各自的特点：

数组：

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

链表：

链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

二、数组和链表的区别：

1、从逻辑结构角度来看：
- 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
- 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
2、数组元素在栈区，链表元素在堆区；

3、从内存存储角度来看：
- (静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
- 链表从堆中分配空间, 自由度大但申请管理比较麻烦。
- 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
- 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
更多相关内容
Python实现的数据结构与算法之链表详解
2020-12-24 13:28:55

本文实例讲述了Python实现的数据结构与算法之链表。分享给大家供大家参考。具体分析如下：一、概述链表（linked list）是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的...

收起

数据结构之链表

千次阅读 2022-04-01 15:12:48

文章目录1.1链表的概念及结构1.2逻辑结构和物理结构1.3单链表的优势1.4单链表的实现1.5完整代码 1.1链表的概念及结构 ...实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试

文章目录

1.1链表的概念及结构
- 1.2逻辑结构和物理结构
- - 1.3单链表的优势
  - - 1.4单链表的实现
    - - 1.5完整代码

1.1链表的概念及结构

概念：

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：
1、单向、双向
2、带头、不带头
3、循环、非循环

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多(单链表最多缺陷)。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.2逻辑结构和物理结构

逻辑结构：逻辑结构是我们想象出来的，比如指针是没有一条线指向变量的地址的，那是我们虚构出来的，是为了方便我们的理解…

物理结构：物理结构是变量实实在在在内存中如何存储的

1.3单链表的优势

首先来说说动态顺序表的优劣势
优势：连续的物理空间，方便下标随机访问
缺陷：1.插入数据，空间不够时，需要扩容
2.头部或中间插入和删除时，需要挪动数据，时间复杂度为O(n)
3.可能存在一点的空间浪费，当扩容越来越大时
4.不能按需申请和释放空间

基于顺序表的劣势，所以设计出了链表，它们是相辅相成的
因为顺序表尾插尾删的时间复杂度都是O(1)，而头插头删时间复杂度是O(n)。但是单链表的头插和头删时间复杂度是O(1)，尾插尾删是O(n)。所以说它们是相辅相成的。
单链表的优势：不需要扩容，插入新数据时直接重新开辟节点，解决了内存浪费和不能按需申请的问题，头插头删时间复杂度为O(1)
单链表的缺陷：不能随机访问，只能往前走，尾插尾删时需要找尾节点，高速缓冲命中率低

1.4单链表的实现

单链表的实现

头文件
开始创建的节点是这样的,每个长方形就是一个节点(结构体指针)
这里很多接口都传二级指针，是因为测试时结构体指针初始化要传"结构体指针的地址"也就是二级指针，才能改变结构体指针所指向的内容。
ps：phead是头节点，指向(存储)第一个节点的地址

#Slist.h
#ifndef SLIST_H_
#define SLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

typedef struct SList
{
    SLTDataType data;   //数据域
    struct SList *next; //指针域
} SListNode;

void SListPrint(SListNode *phead);                                        //显示链表内容
void SListPushBack(SListNode **pphead, SLTDataType x);                    //尾插
void SListPushFront(SListNode **pphead, SLTDataType x);                   //头插
void SListPopBack(SListNode **pphead);                                    //尾删
void SListPopFront(SListNode **pphead);                                   //头删
SListNode *SListFind(SListNode *phead, SLTDataType x);                    //查找值为x的节点
void SListInsert(SListNode **pphead, SListNode *pos, SLTDataType x);      //在pos节点前面插入一个新的节点
void SListErase(SListNode **pphead, SListNode *pos);                      //删除pos节点前面的节点
void SListInsertAfter(SListNode **pphead, SListNode *pos, SLTDataType x); //在pos节点后面插入一个新的节点
void SListEraseAfter(SListNode **pphead, SListNode *pos);                 //删除pos后一个节点的数据
void SListDestory(SListNode **pphead);                                    //释放链表

#endif

实现函数接口：SListPrint()

void SListPrint(SListNode *phead)
{
    //链表一开始为空，无需判断
    SListNode *cur = phead;
    //遍历链表
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        //每次保存下一个节点的地址
        cur = cur->next;
    }
    printf("NULL\n");
}

在这里插入图片描述

实现独立函数接口：BuySListNode() 这个函数是创建新节点

SListNode *BuySListNode(SLTDataType x)
{
    //动态开辟新节点
    SListNode *newNode = (SListNode *)malloc(sizeof(SListNode));
    //判断堆区是否已满，已满则malloc()返回NULL
    if (newNode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        //不为空则把数据给到新节点
        newNode->data = x;
        newNode->next = NULL;
    }
    return newNode;
}

实现函数接口：SListPushBack()

void SListPushBack(SListNode **pphead, SLTDataType x)
{
    //判断二级指针是否为空
    assert(pphead);
    //创建新节点
    SListNode *newNode = BuySListNode(x);
    //节点为空时直接链接
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        //不为空时：找尾->链接
        SListNode *tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        //链接
        tail->next = newNode;
    }
}

节点为空时

节点不为空时

实现函数接口：SListPushFront()

void SListPushFront(SListNode **pphead, SLTDataType x)
{
    //判断二指针是否为空
    assert(pphead);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        newNode->next = *pphead;
        *pphead = newNode;
    }
}

链表节点尾空时

链表节点不为空时

实现函数接口：SListPopBack()

oid SListPopBack(SListNode **pphead)
{
    assert(pphead);
    //如果节点为空，那么不需要删除
    if (*pphead == NULL)
    {
        //结束函数
        return;
    }
    //只有一个节点时，直接释放节点，然后置为NULL
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //多个节点
        SListNode *tail = *pphead;
        SListNode *prev = NULL;
        //找尾前一个节点
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

在这里插入图片描述

函数接口：SListPopFront()

void SListPopFront(SListNode **pphead)
{
    assert(pphead);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        //保存头节点的next节点，否则free后会找不到
        SListNode *next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

函数接口：SListFind()

SListNode *SListFind(SListNode *phead, SLTDataType x)
{
    SListNode *cur = phead;
    while (cur != NULL)
    {
        //逐个节点判断是否有相等的data
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

函数接口：SListInsert()

void SListInsert(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->next == pos)
    {
        //复用头插函数接口
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode *prev = *pphead;
        //找pos前面的节点
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        //链接新节点
        newNode->next = pos;
        prev->next = newNode;
    }
}

在这里插入图片描述

函数接口：SListErase()

void SListErase(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    //节点为空即不用删除
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

在这里插入图片描述

函数接口：SListInsertAfter()

void SListInsertAfter(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *newNode = BuySListNode(x);
        newNode->next = pos->next;
        pos->next = newNode;
    }
}

在这里插入图片描述

函数接口：SListEraseAfter()

void SListEraseAfter(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = pos->next;
        if (next)
        {
            pos->next = next->next;
            free(next);
            next = NULL;
        }
    }
}

在这里插入图片描述

最后一个接口：SListDestory()

void SListDestory(SListNode **pphead)
{
    assert(pphead);
    SListNode *cur = *pphead;
    while (cur != NULL)
    {
        //保存上一个节点地址
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

1.5完整代码

#Slist.h
#ifndef SLIST_H_
#define SLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

typedef struct SList
{
    SLTDataType data;   //数据域
    struct SList *next; //指针域
} SListNode;

void SListPrint(SListNode *phead);                                        //显示链表内容
void SListPushBack(SListNode **pphead, SLTDataType x);                    //尾插
void SListPushFront(SListNode **pphead, SLTDataType x);                   //头插
void SListPopBack(SListNode **pphead);                                    //尾删
void SListPopFront(SListNode **pphead);                                   //头删
SListNode *SListFind(SListNode *phead, SLTDataType x);                    //查找节点
void SListInsert(SListNode **pphead, SListNode *pos, SLTDataType x);      //在pos节点前面插入一个新的节点
void SListErase(SListNode **pphead, SListNode *pos);                      //删除pos节点前面的节点
void SListInsertAfter(SListNode **pphead, SListNode *pos, SLTDataType x); //在pos节点后面插入一个新的节点
void SListEraseAfter(SListNode **pphead, SListNode *pos);                 //删除pos后一个节点的数据
void SListDestory(SListNode **pphead);                                    //释放链表
#endif

#Slist.c
#include "SList.h"

void SListPrint(SListNode *phead)
{
    //链表一开始为空，无need判断
    SListNode *cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SListNode *BuySListNode(SLTDataType x)
{
    SListNode *newNode = (SListNode *)malloc(sizeof(SListNode));
    if (newNode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newNode->data = x;
        newNode->next = NULL;
    }
    return newNode;
}

void SListPushBack(SListNode **pphead, SLTDataType x)
{
    //判断二级指针是否为空
    assert(pphead);
    //创建新节点
    SListNode *newNode = BuySListNode(x);
    //节点为空时直接链接
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        //不为空时：找尾->链接
        SListNode *tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        //链接
        tail->next = newNode;
    }
}

void SListPushFront(SListNode **pphead, SLTDataType x)
{
    //判断二指针是否为空
    assert(pphead);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        newNode->next = *pphead;
        *pphead = newNode;
    }
}

void SListPopBack(SListNode **pphead)
{
    assert(pphead);
    //如果节点为空，那么不需要删除
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode *tail = *pphead;
        SListNode *prev = NULL;
        //找尾上一个节点
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

void SListPopFront(SListNode **pphead)
{
    assert(pphead);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

SListNode *SListFind(SListNode *phead, SLTDataType x)
{
    SListNode *cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void SListInsert(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->next == pos)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        newNode->next = pos;
        prev->next = newNode;
    }
}

void SListErase(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    //节点为空即不用删除
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListInsertAfter(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *newNode = BuySListNode(x);
        newNode->next = pos->next;
        pos->next = newNode;
    }
}

void SListEraseAfter(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = pos->next;
        if (next)
        {
            pos->next = next->next;
            free(next);
            next = NULL;
        }
    }
}

void SListDestory(SListNode **pphead)
{
    assert(pphead);
    SListNode *cur = *pphead;
    while (cur != NULL)
    {
        //保存上一个节点地址
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

#Test.c
#include "Slist.h"
int main()
{
    //尾插
    SListNode *sl = NULL;
    SListPushBack(&sl, 1);
    SListPushBack(&sl, 2);
    SListPushBack(&sl, 3);
    SListPushBack(&sl, 4);
    SListPushBack(&sl, 5);
    SListPrint(sl);

    //头插
    SListPushFront(&sl, 0);
    SListPushFront(&sl, -1);
    SListPushFront(&sl, -2);
    SListPrint(sl);

    //尾删
    SListPopBack(&sl);
    SListPopBack(&sl);
    SListPrint(sl);

    //头删
    SListPopFront(&sl);
    SListPopFront(&sl);
    SListPopFront(&sl);
    SListPrint(sl);

    //查找
    SListNode *pos = SListFind(sl, 3);
    if (pos == NULL)
    {
        printf("没找到...\n");
    }
    else
    {
        printf("找到了: %p\n", pos);
    }

    //随机插入
    SListInsert(&sl, pos, 100);
    SListPrint(sl);

    //随机删除
    SListErase(&sl, pos);
    SListPrint(sl);

    // pos位置后面插入新节点
    SListNode *pos2 = SListFind(sl, 1);
    SListInsertAfter(&sl, pos2, 200);
    SListPrint(sl);

    //删除pos后一位的节点
    SListEraseAfter(&sl, pos2);
    SListPrint(sl);

    //释放链表
    SListDestory(&sl);
    SListPrint(sl);
    return 0;
}

单链表相关知识已经干完了，如有错误请大家指出，感谢！！！

收起

展开全文

c语言开发语言数据结构链表

链表-Java实现链表数据结构

千次阅读 2020-06-08 19:08:07

链表(Linked list)：是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。使用链表结构可以克服数组需要预先知道数据大小的缺点，链表...

链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(“links”)

链表(Linked list)：是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针
域，空间开销比较大。

单向链表

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的 next指向该节点的下一个节点
在这里插入图片描述
在表头增加节点：

在表头删除节点：

/**
 * @author shihaowei
 * @date 2020-06-03 16:28
 */
public class SingleLinkList {

    private int size;
    private Node head;


    public SingleLinkList() {

        this.size = 0;
        this.head = null;
    }

    /** 内部类节点 */
    public class Node {

        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }

    /** 添加节点 */
    public Object addHead(Object obj){

        Node newNode = new Node(obj);
        if (size == 0){
            head = newNode;

        }else {
            newNode.next = head;
            head = newNode;
        }
        size++;
        return obj;
    }

    /** 删除头节点 */
    public Object delHead(){
        if (size > 0){
            Object data = head.data;
            head = head.next;
            size--;
            return data;
        }
        return false;
    }


    /** 获取指定数据节点*/
    public Node find(Object value){

        Node current = head;
        int tempsize = size;
         while (tempsize>0){

             if (current.data.equals(value)){
                 return current;
             }else {
                 current = current.next;
                 tempsize--;
             }
         }
         return null;
    }

    /** 删除数据节点*/
    public boolean delValue(Object value){
        if (size == 0){
            return false;
        }
        Node current = head;
        Node prenode = head;

        while (!current.data.equals(value)){

            if (current.next == null){
                return false;
            }else {
                prenode = current;
                current = current.next;
            }
        }

        //如果第一个节点就是要删除的
        if (current == head){
            head = current.next;
            size--;
        }else {
            prenode.next = current.next;
            size--;
        }

        return true;
    }


    @Override
    public String toString() {
        return "SingleLinkList{" +
                "size=" + size +
                ", head=" + head +
                '}';
    }

    public static void main(String[] args) {

        SingleLinkList linkList = new SingleLinkList();
        linkList.addHead("a");
        linkList.addHead("b");
        linkList.addHead("c");

        //linkList.delHead();
        System.out.println(linkList);
    }


}

双端链表

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。
在这里插入图片描述

public class DoublePointLinklist {

    private Node head;
    private Node tail;
    private int size;

    // 链表的节点类
    private class Node{

        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }

    public DoublePointLinklist() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 头节点插入
     * @param data
     * @return
     */
    public Object addHead(Object data){

        Node node = new Node(data);
        if (head.next == null){
            head = node;
            tail = node;
        }else {
            head.next = head;
            head = node;
        }
        size++;
        return data;

    }

    /**
     * 尾节点插入
     * @param data
     * @return
     */
    public Object addTail(Object data){

        Node node = new Node(data);
        if (head.next == null) {
            head = node;
            tail = node;
        }else {
            tail.next = tail;
            tail = node;
        }
        size++;
        return data;
    }


    /**
     * 删除节点
     * @param data
     * @return
     */
    public boolean delNode(Object data){
        if ( size == 0){
            return false;
        }

        Node prenode = head;
        Node current = head;
        while (!head.data.equals(data)){
            if (current.next == null){
                return false;
            }else {
                prenode = current;
                current = current.next;
            }
        }

        if (current == head){
            head = current.next;
        }else {
            prenode.next = current.next;
        }

        size--;
        return true;
    }
}

双向链表

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历
在这里插入图片描述

package person.shw.datastructure.link;

/**
 * @author shihaowei
 * @date 2020-06-08 16:39
 */
public class TwoWayLinkedList {

    private Node head;
    private Node tail;
    private int size;


    /**
     * 节点类
     */
    private class Node{

        private Object object;
        private Node next;
        private Node pre;

        public Node(Object object) {
            this.object = object;
        }
    }

    public TwoWayLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }


    /**
     * 链表头增加节点
     * @param obj
     */
    public void addHead(Object obj){

        Node node = new Node(obj);

        if (size == 0){
            head = node;
            tail = node;
        }else {
            head.pre = node;
            head.next = head;
            head = node;
        }
        size++;
    }

    /**
     * 链表尾添加节点
     * @param obj
     */
    public void addTail(Object obj){

        Node node = new Node(obj);

        if (size == 0) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            node.pre = tail;
            tail = node;
        }
        size++;
    }


    /**
     * 删除头节点
     * @return
     */
    public Object deleteHead(){

        Node temp = head;

        if (size != 0){
            head = head.next;
            head.pre = null;
            size --;
        }

        return temp;

    }

    /**
     * 删除尾节点
     * @return
     */
    public Object deleteTail(){

        Node temp = tail;

        if (size != 0){
            tail = tail.pre;
            size --;
        }

        return temp;
    }


    /**
     * 获取节点个数
     * @return
     */
   public int getSize(){
        return size;
   }


    /**
     * 显示节点信息
     */
    public void display(){
        if(size >0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){//当前链表只有一个节点
                System.out.println("["+node.object+"]");
                return; }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.object+"->");
                }else if(node.next == null){

                    System.out.print(node.object+"]");
                }else{
                    System.out.print(node.object+"->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println(); }else{//如果链表一个节点都没有，直接打印[]
            System.out.println("[]");
        }
    }

}

有序链表

前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动)，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

public class OrderLinkedList {
  private Node head;
  
  private class Node{
      private int data;
      private Node next;
      public Node(int data){
          this.data = data;
  } 
}
  public OrderLinkedList(){
      head = null;
}
//插入节点，并按照从小打到的顺序排列 public void insert(int value){
      Node node = new Node(value);
      Node pre = null;
      Node current = head;
      while(current != null && value > current.data){
          pre = current;
          current = current.next;
      }
      if(pre == null){
          head = node;
          head.next = current;
      }else{
          pre.next = node;
          node.next = current;
      }
}
//删除头节点
public void deleteHead(){
      head = head.next;
  }
  public void display(){
      Node current = head;
      while(current != null){
          System.out.print(current.data+" ");
          current = current.next;
      }
      System.out.println("");
  }
}

在有序链表中插入和删除某一项最多需要O(N)次比较，平均需要O(N/2)次，因为必须沿着链表上一步一步走才能找到正确的插入位置，然而可以最快速度删除最值，因为只需要删除表头即可，如果一个应用需要频繁的存取最小值，且不需要快速的插入，那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现

总结

上面我们讲了各种链表，每个链表都包括一个LinikedList对象和许多Node对象，LinkedList对象通常包含头和尾节点的引用，分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部分data，以及对上一个节点的引用prev和下一个节点的引用next，只有下一个节点的引用称为单向链表，两个都有的称为双向链表。next值为null则说明是链表的结尾，如果想找到某个节点，我们必须从第一个节点开始遍历，不断通过next找到下一个节点，直到找到所需要的。栈和队列都是ADT，可以用数组来实现，也可以用链表实现

收起

展开全文

链表数据结构 java 算法

数据结构与算法:1.链表结构

千次阅读 2022-03-18 18:14:30

概念：链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种**递归**的数据结构。图示：能保持数据之间的逻辑顺序，但不必按照顺序存储。和C不一样的是python没有专门的指针概念，在...

1 Python链表

1.1基本概念

概念：链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种**递归**的数据结构。

图示：能保持数据之间的逻辑顺序，但不必按照顺序存储。
在这里插入图片描述

和C不一样的是python没有专门的指针概念，在python中每个变量都是指针

链表的删除可以通过修改指针来实现

Python实现链表的方法：

class Node:
    '''
    	data:节点保存的数据
    	_next:保存下一个节点对象
    '''
    def __init__(self,data,pnext=None):
        self.data=data
        self._next=pnext

1.2 链表的基本要素

１．节点，每一个节点有两个域：

左：值域，右：针域

２．head节点：特殊节点，永远指向第一个节点

３．tail节点：特殊节点，永远指向最后一个节点

４．None:链表最后节点的针域的指针指向None值,因此也叫接地点.

class Node:
    def __init__(self,data = None, next = None):
        self.data = data
        self.next = next

创建独立节点:

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

表示节点间关系:

node1.next = node2
node2.next = node3

1.3链表的常用方法

LinkedList() 创建空链表，不需要参数，返回值是空链表
is_empty() 测试链表是否为空，不需要参数，返回值是布尔值
append(data) 在尾部增加一个元素作为列表最后一个，参数是要追加的元素，无返回值
iter() 遍历链表，无参数，无返回值，此方法一般是一个生成器
insert(idx,value) 插入一个元素，参数为插入元素的索引和值
remove(idx)移除1个元素，参数为要移除的元素或索引，并修改链表
size() 返回链表的元素数，不需要参数，返回值是个整数
search(item) 查找链表某元素，参数为要查找的元素或索引，返回是布尔值

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

1.4链表种类

单向链表、单向循环链表、双向链表、双向循环链表。
在这里插入图片描述

两种最简单的链表为单向链表和双向链表。

单向链表通过一个外部的头链接来访问第1项，单向链表的节点被分成两个部分，第一部分保存或显示关于节点的信息，第二部分储存下一节点地址。

单向链表只能向一个方向遍历。单向链表中每个节点只有一个指针。

单向链表结构图:

在这里插入图片描述

双向链表结构图：

链表无法进行随机访问，只能进行顺序访问。
链表分配内存的方式和数组不同，在链表中插入或删除点时，可以直接进行插入或删除，不需要在内存中移动数据项；
每一次插入和删除的过程，链表会调整大小，不需要额外的内存代价，也不需要复制数据项。

1.5遍历链表

链表的基本操作：遍历next节点

在列表中查找一个元素
在列表中插入一个元素
从列表中删除一列元素

probe = head
while probe != None:
    probe = probe.next

注意:

不可以用head来遍历列表，否则会丢失列表的一些节点，可以使用和head相同类型的临时的指针变量，这个变量先初始化为链表结构的head指针，然后控制一个循环。

单向链表遍历为例，流程框图如下：

遍历结束后，temp指针为None，而head指针还是指向第一个节点，遍历在时间上是线性的，并且不需要额外的内存。

遍历单链表结构会访问每一个节点，并且当遇到一个空链接的时候终止，而None就是充当负责停止这个过程的哨兵。

1.6链表运用

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def is_empty(self):
        return self.head is None
    
    def append(self,data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
    
    def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur =cur.next
            yield cur.data
            
    def insert(self, idx, value):
        cur = self.head
        cur_idx = 0
        if cur is None:
            raise Exception("The list is an empty")
        while cur_idx < idx - 1:
            cur = cur.next
            if cur is None:
                raise Exception('......')
            cur_idx = cur_idx + 1
        node = Node(value)
        node.next = cur.next
        cur.next = node
        if node.next is None:
            self.tail = node
            
    def remove(self, idx):
        cur = self.head
        cur_idx = 0
        if self.head is None:  # 空链表时
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:
            cur = cur.next
            if cur is None:
                raise Exception('list length less than index')
            cur_idx += 1
        if idx == 0:   # 当删除第一个节点时
            self.head = cur.next
            cur = cur.next
            return
        if self.head is self.tail:   # 当只有一个节点的链表时
            self.head = None
            self.tail = None
            return
        cur.next = cur.next.next
        if cur.next is None:  # 当删除的节点是链表最后一个节点时
            self.tail = cur
 
            
    def size(self):
        current = self.head
        count = 0
        if current is None:
            return 'The list is an empty list'
        while current is not None:
            count += 1
            current = current.next
        return count
    
    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.data == item:
                found = True
            else:
                current = current.next
        return found

验证操作:

if __name__ == '__main__':
    link_list = LinkedList()
    for i in range(150):
        link_list.append(i)
    
 
print(link_list.is_empty())
 
link_list.insert(10, 30)

收起

展开全文

链表数据结构散列表

数组和链表数据结构描述，各自的时间复杂度
千次阅读 2020-11-26 08:56:33

两种数据结构都是线性表，在排序和查找等算法中都有广泛的应用一、各自的特点：数组：数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一...

收起

java
数据结构-链表篇
千次阅读 2021-09-07 22:54:59

数据结构-链表篇

收起

链表数据结构
Nginx源码初探之数据结构 - 链表数据结构
千次阅读 2020-01-12 13:29:54

由于数据内容存放的是指针，所以理论上ngx_list_t可以用来构建多维链表甚至是网络结构，只是Nginx原始代码封装的函数中并不涉及这些数据结构的操作（实际上也不需要）。 1.数据结构 Nginx链表的数据结构包含两个...

收起
数据结构--链表概念及常见链表结构
千次阅读 多人点赞 2020-12-17 00:09:25

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构由以下8种: 1、不带头单向循环结构 2、不带头单向非循环结构 3、不带头双向循环结构 4、不...

收起

数据结构
js数据结构-链表
千次阅读 2022-01-20 10:41:57

相较于数组数据结构，链表的好处在于添加或移除元素的时候无需移动其他元素。想访问链表中间的某个元素，需要从起点（表头）开始迭代链表直到找到所需元素。⭐️ 链表最后一个节点的下一个元素始终是 undefined 或 ...

收起

链表数据结构 javascript
数据结构 - 链表和数组的区别
千次阅读 2022-02-27 16:00:16

文章目录数据结构 - 链表和数组的区别1、在内存上2、时间复杂度3、链表的结构4、各自的优缺点5、为什么使用较常用的是单头链表 数据结构 - 链表和数组的区别 1、在内存上数组是连续内存，因为是静态分配，所以不可...

收起

链表数据结构散列表数组
【数据结构】链表
千次阅读 2022-03-12 16:41:05

链表

收起

数据结构链表
数据结构——链表的实现
2017-12-29 17:44:08

数据结构课程的链表类的C++实现，搜索，删除，插入，查找等函数

收起

链表
数据结构—单向链表（详解）
千次阅读 2022-03-16 10:27:28

基于C语言的链表基础，包括概念，链表的初始化，插入，删除，查找等操作。

收起

数据结构链表
数据结构大总结（链表篇）
千次阅读 2021-11-18 20:08:37

顺序表和链表1.线性表2.顺序表3.链表4.顺序表和链表的区别和联系一.算法的时间复杂度和空间复杂度 1.算法效率算法的复杂度： 1.算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一...

收起

c语言算法 c++
C++数据结构——链表
千次阅读 2018-06-27 22:03:59

C++数据结构——链表参考博客：（1）实践：https://www.cnblogs.com/renyuan/archive/2013/05/21/3091524.html（2）实践：https://blog.csdn.net/lg1259156776/article/details/47021505（3）理论：数据结构（二）...

收起

线性表链表数据结构
数据结构-链表 数据结构 链表
2010-05-04 15:27:04

数据结构-链表链表:是用一组地址任意的存储单元存放线性表的各个数据元素,通过保存直接后继的存储位置来表示元素之间的逻辑关系; 结点是链表的基本存储单位,每个结点在链表中使用一块连续的存储空间,而相邻结点...

收起
数据结构基于VS平台实现的所有链表结构的基础操作
2022-08-01 19:57:27

数据结构基于VS平台实现的所有链表结构的基础操作数据结构基于VS平台实现的所有链表结构的基础操作数据结构基于VS平台实现的所有链表结构的基础操作数据结构基于VS平台实现的所有链表结构的基础操作数据结构基于VS...

收起
静态链表 ( 数据结构 )
千次阅读 2022-04-16 18:05:21

静态链表什么是静态链表定义结点的定义链表的定义常用操作1. 添加2. 访问什么是静态链表静态链表( static linked list ), 就是用数组来表示链表,用数组元素的下标来模拟链表的指针. 由于是利用数组来定义的链表,...

收起

数据结构 c++ 算法
Java数据结构之双向链表（配图详解，简单易懂）
千次阅读 多人点赞 2022-01-28 19:43:27

Java数据结构之双向链表（配图详解，简单易懂）

收起

链表数据结构 java
数据结构特性解析 (三) 链表
千次阅读 2020-06-30 17:44:21

链表是一种比较简单的数据结构,你可以在编程环境下轻松写出一个链表,甚至生活中也有很多链表的提现,比如铁链,文章底部的下一篇上一篇都可以称作链表数据结构 描述链表像铁链一样,一个链节点连着另一个或另两个...

收起

java 数据结构链表
干货:一文弄懂链表结构,以后再也别问我什么是链表数据结构啦!
千次阅读 2019-04-01 21:22:25

链表 [Linked List]：链表是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构【节点】，按特定的顺序链接在一起的抽象数据类型。链表常用的有 3 类：单链表、双向链表、循环链表。链表的核心操作集有 ...

收起

链表结构
数据结构—双向链表（详解）
千次阅读 2022-03-18 11:05:52

双向链表在之前一篇文章中介绍了单向链表的实现，可以看出单向链表实现过程中，只能够逐次向下继续查找，指针一直指向下一个.../* 双向链表的结构 */ typedef struct llist_st { int data; struct llist_st * prev;

收起

数据结构链表
数据结构-链表-单链表（java实现）
千次阅读 2020-06-20 08:34:05

今天和大家分享数据结构中链表的相关知识。在数据结构中有线性结构和非线性结构两种类别的区分，虽然链表属于线性结构是有序的列表，但是它在内存中却是不连续的。链表分为单链表、双链表、循环链表。下面我就给大家...

收起

java 数据结构链表
linux内核链表（一套精彩的链表数据结构）
2011-04-27 16:44:02

内核链表的构造与操作：在Linux内核中使用了大量的链表结构来组织数据。这些链表大多数采用了.../linux/list.h中实现的一套精彩的链表数据结构。内核的链表具备双链表功能，实际上，通常它都的组织成双向循环链表。

收起

内核链表
Python 链表数据结构 理解以及实现
千次阅读 2020-02-14 11:28:38

为什么Python没有链表数据结构的标准库Python基础数据结构的时间复杂度-List,Set,Dict,Collections.deque(1)List(2)collections.deque(3)set(4)dict2. Python实现链表 Python 的标准库并没有实现链表这种数据结构的...

收起
链表数据结构图解
千次阅读 2019-05-06 16:44:47

项目中经常会用到LinkedList集合来存储数据，打算写一篇LinkedList的源码解析，而LinkedList是基于链表结构存储数据的，这篇博文将解析链表数据结构，包括单向链表和双向链表； 1：单向链表：单向链表的链表对象...

收起
数据结构——链表（定义详解及建立单链表与实现其操作）
千次阅读 2021-01-28 22:23:30

链表定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括...

收起

链表数据结构
链表数据结构特点
万次阅读 2017-11-14 11:25:36

链表数据结构的特点为了简便，这里以单链表为例子说明，为了便于读者理解，这里和数组作为对比。在数组中，是通过索引访问元素的，但是不要小看索引，好多精妙的算法都是利用了这个索引玩花样。但是链表不能，只能...

收起

单链表数据结构
链表数据结构的创建和调用（C++）
千次阅读 2020-02-04 23:24:43

本文主要总结链表的基本编程用法，通过创建一个链表和调用链表每个节点的数据代码，展示基本的链表数据结构用法。 1.1原理讲解链表是在物理上可以是非连续的存储空间，由一片片存储区域组成，每个存储区域又被...

收起

链表创建 C++ list 调用

两种数据结构都是线性表，在排序和查找等算法中都有广泛的应用

一、各自的特点：

数组：

链表：

二、数组和链表的区别：

Python实现的数据结构与算法之链表详解

数据结构之链表

文章目录

1.1链表的概念及结构

1.2逻辑结构和物理结构

1.3单链表的优势

1.4单链表的实现

1.5完整代码

链表-Java实现链表数据结构

单向链表

双端链表

双向链表

有序链表

总结

数据结构与算法:1.链表结构

1 Python链表

1.1基本概念

1.2 链表的基本要素

1.3链表的常用方法

1.4链表种类

1.5遍历链表

1.6链表运用

数组和链表数据结构描述，各自的时间复杂度

数据结构-链表篇

Nginx源码初探之数据结构 - 链表数据结构

数据结构--链表概念及常见链表结构

js数据结构-链表

数据结构 - 链表和数组的区别

【数据结构】链表

数据结构——链表的实现

数据结构—单向链表（详解）

数据结构大总结（链表篇）

C++数据结构——链表

数据结构-链表 数据结构 链表

数据结构基于VS平台实现的所有链表结构的基础操作

静态链表 ( 数据结构 )

Java数据结构之双向链表（配图详解，简单易懂）

数据结构特性解析 (三) 链表

干货:一文弄懂链表结构,以后再也别问我什么是链表数据结构啦!

数据结构—双向链表（详解）

数据结构-链表-单链表（java实现）

linux内核链表（一套精彩的链表数据结构）

Python 链表数据结构 理解以及实现

链表数据结构图解

数据结构——链表（定义详解及建立单链表与实现其操作）

链表数据结构特点

链表数据结构的创建和调用（C++）

链表数据结构

数据结构-链表数据结构链表

Python 链表数据结构理解以及实现