Technology Sharing

Data structure: sequential storage linear table implementation detailed explanation and examples (C, C#, C)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Table of Contents


insert image description here

A sequential storage linear list is a basic data structure that stores the elements of a linear list in a set of storage units with consecutive addresses in a certain order. In this blog, we will introduce the implementation of a sequential storage linear list in detail, and use three programming languages, C, C# and C++, as examples to show how to implement a sequential storage linear list.

1. Basic concepts of sequential storage linear table

Sequential storage linear table is a way to implement a linear table, which has the following characteristics:

The elements are of the same type: The elements in the sequentially stored linear list are of the same type, and each element occupies a certain amount of storage space.
Elements are ordered: The elements in a sequentially stored linear list are arranged in a certain order, usually in non-decreasing order.
Random access: Sequential storage linear tables support random access, that is, any element in the table can be directly accessed through an index.
Dynamic expansion: Sequential storage linear tables can dynamically expand storage space as needed to accommodate more elements.

2. Implementation of Sequential Storage Linear Table

1. Data structure definition

First, we need to define a data structure for sequential storage linear lists. Taking C language as an example, we can use a structure (struct) to define it:

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

typedef struct {
    int *data; // 指向动态分配的数组
    int size;  // 线性表的当前长度
    int capacity; // 线性表的容量
} SequenceList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2. Initialization

Initialize the sequential storage linear table and allocate its initial capacity. In C language, we can use the malloc function to dynamically allocate memory:

void initSequenceList(SequenceList *list, int capacity) {
    list->data = (int *)malloc(capacity * sizeof(int));
    if (list->data == NULL) {
        exit(-1); // 内存分配失败，退出程序
    }
    list->size = 0;
    list->capacity = capacity;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3. Add elements

Add elements to a sequential storage linear list. If the current capacity is not enough to accommodate the new elements, you need to expand the capacity first:

void appendSequenceList(SequenceList *list, int value) {
    if (list->size == list->capacity) {
        // 扩展容量
        int newCapacity = list->capacity * 2;
        int *newData = (int *)malloc(newCapacity * sizeof(int));
        if (newData == NULL) {
            exit(-1); // 内存分配失败，退出程序
        }
        for (int i = 0; i < list->size; i++) {
            newData[i] = list->data[i];
        }
        free(list->data);
        list->data = newData;
        list->capacity = newCapacity;
    }
    list->data[list->size++] = value;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

4. Accessing Elements

Access the specified element in the sequential storage linear list:

int getSequenceList(const SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return -1; // 索引无效，返回-1
    }
    return list->data[index];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

5. Modify elements

Modify the specified element in the sequential storage linear list:

void setSequenceList(SequenceList *list, int index, int value) {
    if (index < 0 || index >= list->size) {
        return; // 索引无效，不进行操作
    }
    list->data[index] = value;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

6. Deleting Elements

Delete the specified element in the sequential storage linear list:

void removeSequenceList(SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return; // 索引无效，不进行操作
    }
    for (int i = index + 1; i < list->size; i++) {
        list->data[i - 1] = list->data[i];
    }
    list->size--;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

7. Destruction

Destroy the sequential storage linear table and release the allocated memory:

void destroySequenceList(SequenceList *list) {
    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

3. Examples

Below we use three programming languages, C, C# and C++, to implement a sequential storage linear list, and add, delete, access and print elements in the linear list.

C language example

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

typedef struct {
    int *data;
    int size;
    int capacity;
} SequenceList;

void initSequenceList(SequenceList *list, int capacity) {
    list->data = (int *)malloc(capacity * sizeof(int));
    if (list->data == NULL) {
        exit(-1);
    }
    list->size = 0;
    list->capacity = capacity;
}

void appendSequenceList(SequenceList *list, int value) {
    if (list->size == list->capacity) {
        int newCapacity = list->capacity * 2;
        int *newData = (int *)malloc(newCapacity * sizeof(int));
        if (newData == NULL) {
            exit(-1);
        }
        for (int i = 0; i < list->size; i++) {
            newData[i] = list->data[i];
        }
        free(list->data);
        list->data = newData;
        list->capacity = newCapacity;
    }
    list->data[list->size++] = value;
}

int getSequenceList(const SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return -1;
    }
    return list->data[index];
}

void setSequenceList(SequenceList *list, int index, int value) {
    if (index < 0 || index >= list->size) {
        return;
    }
    list->data[index] = value;
}

void removeSequenceList(SequenceList *list, int index) {
    if (index < 0 || index >= list->size) {
        return;
    }
    for (int i = index + 1; i < list->size; i++) {
        list->data[i - 1] = list->data[i];
    }
    list->size--;
}

void destroySequenceList(SequenceList *list) {
    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

int main() {
    SequenceList list;
    initSequenceList(&list, 10);
    appendSequenceList(&list, 1);
    appendSequenceList(&list, 2);
    appendSequenceList(&list, 3);
    printf("Get element at index 1: %dn", getSequenceList(&list, 1));
    setSequenceList(&list, 1, 4);
    printf("Get element at index 1 after modification: %dn", getSequenceList(&list, 1));
    removeSequenceList(&list, 0);
    printf("Get element at index 0 after removal: %dn", getSequenceList(&list, 0));
    destroySequenceList(&list);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

C# language examples

using System;

public class SequenceList
{
    private int[] data;
    private int size;
    private int capacity;

    public SequenceList(int capacity)
    {
        this.data = new int[capacity];
        this.size = 0;
        this.capacity = capacity;
    }

    public void Append(int value)
    {
        if (size == capacity)
        {
            int newCapacity = capacity * 2;
            int[] newData = new int[newCapacity];
            for (int i = 0; i < size; i++)
            {
                newData[i] = data[i];
            }
            data = newData;
            capacity = newCapacity;
        }
        data[size++] = value;
    }

    public int Get(int index)
    {
        if (index < 0 || index >= size)
        {
            return -1;
        }
        return data[index];
    }

    public void Set(int index, int value)
    {
        if (index < 0 || index >= size)
        {
            return;
        }
        data[index] = value;
    }

    public void RemoveAt(int index)
    {
        if (index < 0 || index >= size)
        {
            return;
        }
        for (int i = index + 1; i < size; i++)
        {
            data[i - 1] = data[i];
        }
        size--;
    }

    public void Clear()
    {
        size = 0;
    }
}

class Program
{
    static void Main(string[] args)
    {
        SequenceList list = new SequenceList(10);
        list.Append(1);
        list.Append(2);
        list.Append(3);
        Console.WriteLine("Get element at index 1: " + list.Get(1));
        list.Set(1, 4);
        Console.WriteLine("Get element at index 1 after modification: " + list.Get(1));
        list.RemoveAt(0);
        Console.WriteLine("Get element at index 0 after removal: " + list.Get(0));
        list.Clear();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

C++ Language Examples

#include <iostream>

class SequenceList {
private:
    int *data;
    int size;
    int capacity;

public:
    SequenceList(int capacity) {
        data = new int[capacity];
        size = 0;
        capacity = capacity;
    }

    void Append(int value) {
        if (size == capacity) {
            int newCapacity = capacity * 2;
            int *newData = new int[newCapacity];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
            capacity = newCapacity;
        }
        data[size++] = value;
    }

    int Get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        return data[index];
    }

    void Set(int index, int value) {
        if (index < 0 || index >= size) {
            return;
        }
        data[index] = value;
    }

    void RemoveAt(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
    }

    void Clear() {
        size = 0;
    }
};

int main() {
    SequenceList list(10);
    list.Append(1);
    list.Append(2);
    list.Append(3);
    std::cout << "Get element at index 1: " << list.Get(1) << std::endl;
    list.Set(1, 4);
    std::cout << "Get element at index 1 after modification: " << list.Get(1) << std::endl;
    list.RemoveAt(0);
    std::cout << "Get element at index 0 after removal: " << list.Get(0) << std::endl;
    list.Clear();
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71

In these three examples, we define a sequential storage linear list class and provide a series of basic operations such as adding, deleting, accessing, and printing elements. Through these examples, you can understand how to implement sequential storage linear lists in different programming languages.

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail