Связанный список против массива

Автор оригинала: Pankaj Kumar.

Связанный список и массив, вероятно, являются наиболее основными структурами данных, но их использование часто может быть запутано. Использование соответствующей структуры данных может часто приводить к более прощему и более эффективному коду. Связанный список VS Array также является популярным интервью в структурах данных.

Связанный список против массива

Эта статья предоставит углубленное сравнение этих двух структур данных.

Мы сравним их на основе следующих свойств:

Определения и структуры
Операции и анализ сложности времени
Анализ памяти
Коды (C и Python)

1. Определения и структуры

Связанный список – это структура данных, которая хранит линейно подключенные, нереационные данные через ссылки. Это означает, что каждый узел связанного списка будет содержать ссылку на его следующий и/или предыдущий узел. Это помогает сделать цепочку узлов, которые линейно связаны, но в памяти они могут не быть в смежном сегменте.

Массив представляет собой структуру данных, которая имеет фиксированный размер и содержит набор данных аналогичного типа, который может быть указан через индексацию. Это означает, что перед использованием массива мы должны определить его размер и тип и после хранения данных, которые мы можем обратиться к нему, используя индексацию.

В памяти массивы также присутствуют в смежном блоке данных.

2D массивы

2. Анализ сложности работы и времени

Мы будем сравнивать структуры данных, основанные на следующих операциях:

Вставка и удаление
Доступ к элементам

Вставка и удаление

Вставка и удаление в связанном списке могут быть выполнены в начале, в середине или в конце.

Если в начале выполняется вставка или удаление, то нам просто нужно переназначить ссылки на голову, таким образом, это операция O (1).
Если вставка или удаление выполнено в середине или в конце, то сначала нам необходимо добраться до необходимого положения в O (N), а затем переназначить ссылки в O (1) время. Это принимает o (n + (n) время.

Связанный список вставка

Для массива, везде, где выполняется вставка или удаление, нам всегда нужно перемещать остаток массива, чтобы сбалансировать индексацию, таким образом, эти операции принимают O (1) время для выполнения операции и O (N) для балансировки индексации. Таким образом, требуется O (N + (N) время всегда.

Вставка массива

Доступ к элементам

В связанном списке для доступа к элементу мы должны достичь его позиции через обход с начала, который принимает o (n) время.

В массиве у нас есть индексы, к которым мы можем напрямую обращаться. Это полезно, потому что теперь нам не нужно делать обход, и, таким образом, доступ к тому, что принимает время O (1).

3. Анализ памяти

Связанный список – почти Всегда более эффективный способ хранения данных. Это связано с тем, что мы назначаем данные в связанный список динамически, и его размер можно уменьшить и расширяться в соответствии с использованием.

Массивы с другой стороны, всегда имеют фиксированный размер. Если элемент не назначается никакого значения, то он по-прежнему остается частью массива и все равно будет использовать память.

Но это не означает, что массивы всегда менее эффективны. Массивы занимают только память, которую они назначены, тогда как связанный список примет память для хранения данных, а также хранения ссылок. Кроме того, для некоторых операций, таких как сортировка, нам нужно дополнительное место для хранения и сдвига элементов, что эффективно в массивах.

Связанные реализации списка

1. Питон

class Node:

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


class LinkedList:
    """
    Initialize the list by assigning
    head = NULL.
    """

    def __init__(self):
        self.head = None

    '''
    Returns the linear traversal of the
    Linked List in the form of a list.

    Initially, we can define a node that 
    points to the head of the linked list
    and then we can keep sending it forward 
    in the Linked List till we don't hit an end.
    '''

    def traverse_list(self):

        # Node that points to the head, initially.
        cur = self.head
        ret = []

        # Loop to send the cur node to the end.
        while cur:
            ret.append(cur.data)
            cur = cur.next

        # Returns the Linear Traversal in a list.
        return ret

    '''
    To insert a node, we have 3 cases:
    1) Empty List
    2) Insertion at the beginning
    3) Insertion in the middle/at the end

    For insertion at the end, we can loop till
    one element before the required position 
    and then do the relinking of references.
    '''

    def insert_node(self, pos, data):

        new_node = Node(data)
        cur_node = self.head

        # Case 1 : Empty List
        if cur_node is None:
            self.head = new_node

        # Case 2: Insertion at the beginning
        elif pos == 0:
            new_node.next = self.head
            self.head = new_node

        # Case 3: Insertion in the middle/at the end
        else:
            while pos - 1 > 0 and cur_node.next is not None:
                cur_node = cur_node.next
                pos -= 1

            next_node = cur_node.next
            new_node.next = next_node
            cur_node.next = new_node

        return True

    '''
    To delete a node, we have 5 cases:
    1) Deletion from Empty List
    2) Deletion at the beginning
    5) Delete a node that does not exist
    3) Deletion at the end
    4) Deletion in the middle

    For deletion of a node, we first reach
    one node before the required position
    through a linear traversal and then relink
    the references accordingly.
    '''

    def remove_node(self, pos):

        # Case 1 : Empty List
        if self.head is None:
            return False

        # Case 2 : Deletion at beginning
        elif pos == 0:
            self.head = self.head.next
            return True

        else:
            cur = self.head
            while pos - 1 > 0 and cur is not None:
                cur = cur.next
                pos -= 1

            # Case 3 : Delete a node that does not exist
            if cur is None:
                return False

            # Case 4: Deletion at the end
            elif cur.next is None:
                cur = self.head
                while cur.next.next is not None:
                    cur = cur.next
                cur.next = None
                return True

            # Case 5 : Deletion in the middle
            cur.next = cur.next.next
            return True


a = LinkedList()
a.insert_node(0, 3)
a.insert_node(0, 2)
a.insert_node(0, 1)
print("Linked List :", a.traverse_list())
a.remove_node(2)
print("Linked list :", a.traverse_list())

Выход

2. C.

#include
#include
#include

struct node{
    int data;
    struct node *next;
} *head = NULL;

struct node *make_node(int data){
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->next = NULL; 
    new->data = data;
    return new;
}

/*
To insert a node, we have 3 cases:
1) Empty List
2) Insertion at the beginning
3) Insertion in the middle/at the end

For insertion at the end, we can loop till
one element before the required position 
and then do the relinking of references.
*/

bool insertNode(int pos, int data){
    struct node *newNode = make_node(data), *curNode = head;

    //Case 1 : Empty List
    if(curNode == NULL){
        head = newNode;
    }

    //Case 2: Insertion at the beginning
    else if(pos == 0){
        newNode->next = head;
        head = newNode;
    }

    //Case 3: Insertion in the middle/at the end
    else{
        while(pos - 1 > 0 && curNode->next != NULL){
            curNode = curNode->next;
            pos--;
        }
        newNode->next = curNode->next;
        curNode->next = newNode;
    }

    return true;
}

/*
Initially we can define a node that 
points to the head of the linked list
and then we can keep sending it forward 
in the Linked List till we don't hit an end.
*/
void traverseList(){
    struct node *cur = head;
    while(cur){
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/*
To delete a node, we have 5 cases:
1) Deletion from Empty List
2) Deletion at the beginning
5) Delete a node that does not exist
3) Deletion at the end
4) Deletion in the middle

For deletion of a node, we first reach
one node before the required position
through a linear traversal and then relink
the references accordingly.
*/

bool removeNode(int pos){

    struct node *cur;

    //Case 1 : Empty List
    if(head == NULL)
        return false;

    //Case 2 : Deletion at beginning
    else if (pos == 0){
        head = head->next;
        return true;
    }

    else{

        cur = head;
        while (pos - 1 > 0 && cur != NULL){
            cur = cur->next;
            pos--;
        }

        //Case 3 : Delete a node that does not exist
        if(cur == NULL)
            return false;

        //Case 4: Deletion at the end
        else if(cur->next == NULL){
            cur = head;
            while(cur->next->next != NULL){
                cur = cur->next;
            }
            cur->next = NULL;
            return true;
        }

        //Case 5 : Deletion in the middle
        cur->next = cur->next->next;
        return true;
    }
}

int main(){

    insertNode(0, 3);
    insertNode(0, 2);
    insertNode(0, 1);

    traverseList();
    removeNode(3);
    traverseList();

    return 0;
}

Выход

Реализации массивов

1. Питон

N = 10
singleDimensionalArray = [0 for i in range(N)]
multiDimensionalArray = [[0 for x in range(N)] for y in range(N)]

A = 4
pos = 5
singleDimensionalArray[pos] = A

X, Y = 2, 3
multiDimensionalArray[X][Y] = A

print(singleDimensionalArray)

for i in multiDimensionalArray:
    print(i)

Выход :

2. C.

#include
#include
#include

#define N 5

int main(){

    int singleDimensionalArray[N] = {0};
    int multiDimensionalArray[N][N] = {0};

    int A = 4;
    int pos = 3, X = 2, Y = 3;

    singleDimensionalArray[pos] = A;
    multiDimensionalArray[X][Y] = A;

    int i, j;
    for(i = 0; i < N; i++){
        printf("%d ", singleDimensionalArray[i]);
    }
    printf("\n\n");

    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            printf("%d ", multiDimensionalArray[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Выход

Связанный список против массива

1. Определения и структуры

2. Анализ сложности работы и времени

Вставка и удаление

Доступ к элементам

3. Анализ памяти

Связанные реализации списка

1. Питон

2. C.

Реализации массивов

1. Питон

2. C.

Читайте ещё по теме: