Как вы реализуете связанный список в массиве?

Question

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

Хотя я могу представить, как это сделать с несколькими массивами, как это можно сделать с одним массивом?

РЕДАКТИРОВАТЬ: Может ли это быть сделано эффективно, учитывая, что элементы должны быть удалены и вставлены из списка - предположительно, требуется идентификация свободных элементов в массиве?

Answer 1

Если это массив объектов, то каждый объект будет хранить значение и указатель на следующий объект.

[0] -> {"a",1}
[1] -> {"b",2}
[2] -> {"c",4}
[3] -> {"1",5}
[4] -> {"d",7}
[5] -> {"2",6}
[6] -> {"3",8}
[7] -> {"e",-1}
[8] -> {"4",-1}

Итак, у меня есть 2 связанных списка, первый:

"a" -> "b" -> "c" -> "d" -> "e"

и второй:

«1» -> «2» -> «3» -> «4»

оба используют индекс -1 как конец списка.

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

Честно говоря, я даже не уверен, что понимаю вопрос, но все равно хотел выбросить идеи.

Answer 2

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

Answer 3

Как вы реализуете связанный список в массиве?

Вот возможный подход ^{(с использованием C ++)} : ваш узел будет состоять из индексов для следующих и предыдущих элементов в списке :

struct Link
{
    // additional data
    int next;
    int prev;
};

где next и prev будут содержать индексы массива, хранящего Link s.

Link** head; // = new Link*[initial_size];
int first;  // -1 initially (analogue of nullptr)
int last;   // index of the last element in the array: head

дополнительно должен быть механизм учета доступных элементов в массиве, более наивная реализация может быть:

bool* available; // = new bool[initial_size]; // all initialized to true

вам потребуются функции для получения индекса из bool available (указывающего на отсутствие узла в индексе, i в head, где элемент available имеет значение true). Например:

int get_available_index()
{
    for (int i = 0; i < initial_size; ++i)
    {
        if (available[i] == true)
        {
            available[i] == false;
            return i;
        }
    }
    // indicate / throw list full / resize???
}

Вот как puch_back() может выглядеть:

void push_back(Link** head, Link* new_link)
{
    // chech pointer validity

    int index = get_available_index();

    // probably using: placement new(), to construct a node in that location
    // new(head + index) new_link;? or just
    head[index] = new_link;

    if (last != -1) // list not empty
    {
        head[last]->next = index;
        head[index]->prev = (last - head[0]); // gives you the index of the last node
    }
    else
    {
        first = index;
        head[index]->prev = -1;
    }

    last = index;
    head[index]->next = -1;
}

Кроме того, должна быть функция, обратная к get_available_index(), в которой элемент available[i] имеет значение true (а объект уничтожен (head + i)->~Link();?)

Может ли это быть эффективно сделано с учетом того, что элементы должны быть удалены и вставлены из списка - предположительно, требующих идентификации свободных элементов в массиве?

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

Answer 4

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

Хорошая и простая реализация - из операционной системы Contiki (BSD).лицензии), см. реализацию memb и список .

Вы используете их следующим образом:

struct connection {
    struct connection *next;
    /* ... */
};

/* This allocates a fixed size array of 16 'struct connection' */
MEMB(connection_mem, struct connection, 16);

/* This is just a void ** keeping track of list elements in a linked list */
LIST(connection_list);

void main()
{
    /* Initialize the memory block */
    memb_init(&connection_mem);

    /* Allocate a new chunk */
    struct connection *c = memb_alloc(&connection_mem);
    if(c != NULL) {
        /* Add to list */
        list_add(connection_list, c);
    }

    for(c = list_head(connection_list); c != NULL; c = c->next) {
        /* ... */
    }
}

Редактировать Извините, вы не упомянули какой-либо конкретный язык программирования, и я в основном знаком с C и C ++.Если вы можете расшифровать, как реализованы memb и list, тогда основная теория должна быть такой же: простой распределитель блоков, отслеживающий свободные / использованные блоки, и реализация связанного списка, которая может ссылаться на эти отдельные блоки.

Answer 5

В C ++ я быстро написал это, и это работает. Каждый индекс в массиве содержит двусвязный список.

#include <list>
#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
  list<int> ll[10];
  for (int i = 0; i < 10; i++)
    for (int j = 100; j > 0; j-=10)
      ll[i].push_back(j);

  list<int>::iterator it;
  for (int i = 0; i < 10; i++)
  {
    for (it = ll[i].begin(); it != ll[i].end(); it++)
    {
      cout << " " << *it;
    }
    cout << endl;
  }
  return 0;
}

выход:

$ g++ ll-in-array.cpp && ./a.out
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10
 100 90 80 70 60 50 40 30 20 10