C Language
Liste collegate

Osservazioni

struct singly_node
{
  struct singly_node * next;
};

struct doubly_node
{
  struct doubly_node * prev;
  struct doubly_node * next;
};

void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
  prev->next = next;
  next->prev = prev;
}

void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
  doubly_node_bind (head, head);
}

void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
  head->prev = NULL;
  tail->next = NULL;
  doubly_node_bind (head, tail);
}

void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
  doubly_node_bind (prev, insertion);
  doubly_node_bind (insertion, next);
}

void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
  doubly_node_insert_between (tail->prev, tail, insertion);
}

void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
  doubly_node_insert_between (head, head->next, insertion);
}

Inserimento di un nodo all'inizio di una lista concatenata

Il codice seguente richiederà i numeri e continuerà ad aggiungerli all'inizio di un elenco collegato.

/* This program will demonstrate inserting a node at the beginning of a linked list */

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

struct Node {
  int data;
  struct Node* next;
};


void insert_node (struct Node **head, int nodeValue);
void print_list (struct Node *head);

int main(int argc, char *argv[]) {
  struct Node* headNode;
  headNode = NULL; /* Initialize our first node pointer to be NULL. */
  size_t listSize, i;
  do {
    printf("How many numbers would you like to input?\n");
  } while(1 != scanf("%zu", &listSize));

  for (i = 0; i < listSize; i++) {
    int numToAdd;
    do {
      printf("Enter a number:\n");
    } while (1 != scanf("%d", &numToAdd));

    insert_node (&headNode, numToAdd);
    printf("Current list after your inserted node: \n");
    print_list(headNode);
  }

  return 0;
}

void print_list (struct Node *head) {
  struct node* currentNode = head;

  /* Iterate through each link. */
  while (currentNode != NULL) {
      printf("Value: %d\n", currentNode->data);
      currentNode = currentNode -> next;
  }
}

void insert_node (struct Node **head, int nodeValue) {
  struct Node *currentNode = malloc(sizeof *currentNode);
  currentNode->data = nodeValue;
  currentNode->next = (*head);

  *head = currentNode;
}

Spiegazione per l'inserimento di nodi

Per capire in che modo aggiungiamo i nodi all'inizio, diamo un'occhiata ai possibili scenari:

1. L'elenco è vuoto, quindi è necessario aggiungere un nuovo nodo. In questo caso, la nostra memoria appare come questa dove HEAD è un puntatore al primo nodo:

| HEAD | --> NULL

La riga currentNode->next = *headNode; assegnerà il valore di currentNode->next a essere NULL poiché headNode originariamente parte da un valore di NULL .

Ora, vogliamo impostare il nostro puntatore del nodo principale in modo che punti al nostro nodo corrente.

  -----      -------------
 |HEAD | --> |CURRENTNODE| --> NULL /* The head node points to the current node */
  -----      -------------

Questo è fatto con *headNode = currentNode;

2. L'elenco è già compilato; dobbiamo aggiungere un nuovo nodo all'inizio. Per semplicità, iniziamo con 1 nodo:

 -----    -----------
 HEAD --> FIRST NODE --> NULL
 -----    -----------

Con currentNode->next = *headNode , la struttura dati appare così:

 ---------        -----    ---------------------
 currentNode -->  HEAD --> POINTER TO FIRST NODE --> NULL
 ---------        -----    ---------------------

Che, ovviamente, deve essere modificato poiché *headNode dovrebbe puntare a currentNode .

 ----    -----------    ---------------
 HEAD -> currentNode -->     NODE       -> NULL
 ----    -----------    ---------------

Questo è fatto con *headNode = currentNode;

Inserimento di un nodo in corrispondenza dell'ennesimo posto

Finora, abbiamo esaminato l' inserimento di un nodo all'inizio di una lista concatenata . Tuttavia, la maggior parte delle volte vorrai essere in grado di inserire anche i nodi altrove. Il codice scritto qui sotto mostra come è possibile scrivere una funzione insert() per inserire nodi ovunque negli elenchi collegati.

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

struct Node {
  int data;
  struct Node* next;
};

struct Node* insert(struct Node* head, int value, size_t position);
void print_list (struct Node* head);

int main(int argc, char *argv[]) {
  struct Node *head = NULL; /* Initialize the list to be empty */

  /* Insert nodes at positions with values: */
  head = insert(head, 1, 0);
  head = insert(head, 100, 1);
  head = insert(head, 21, 2);
  head = insert(head, 2, 3);
  head = insert(head, 5, 4);
  head = insert(head, 42, 2);

  print_list(head);
  return 0;
}

struct Node* insert(struct Node* head, int value, size_t position) {
  size_t i = 0;
  struct Node *currentNode;

  /* Create our node */
  currentNode = malloc(sizeof *currentNode);
  /* Check for success of malloc() here! */

  /* Assign data */
  currentNode->data = value;

  /* Holds a pointer to the 'next' field that we have to link to the new node.
     By initializing it to &head we handle the case of insertion at the beginning. */
  struct Node **nextForPosition = &head;
  /* Iterate to get the 'next' field we are looking for.
     Note: Insert at the end if position is larger than current number of elements. */
  for (i = 0; i < position && *nextForPosition != NULL; i++) {
      /* nextForPosition is pointing to the 'next' field of the node.
         So *nextForPosition is a pointer to the next node.
         Update it with a pointer to the 'next' field of the next node. */
      nextForPosition = &(*nextForPosition)->next;
  }

  /* Here, we are taking the link to the next node (the one our newly inserted node should
  point to) by dereferencing nextForPosition, which points to the 'next' field of the node
  that is in the position we want to insert our node at.
  We assign this link to our next value. */
  currentNode->next = *nextForPosition;

  /* Now, we want to correct the link of the node before the position of our
  new node: it will be changed to be a pointer to our new node. */
  *nextForPosition = currentNode;

  return head;
}

void print_list (struct Node* head) {
  /* Go through the list of nodes and print out the data in each node */
  struct Node* i = head;
  while (i != NULL) {
    printf("%d\n", i->data);
    i = i->next;
  }
}

Inversione di una lista collegata

È anche possibile eseguire questa attività in modo ricorsivo, ma in questo esempio ho scelto di utilizzare un approccio iterativo. Questa attività è utile se si inseriscono tutti i nodi all'inizio di un elenco collegato . Ecco un esempio:

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

#define NUM_ITEMS 10

struct Node {
  int data;
  struct Node *next;
};

void insert_node(struct Node **headNode, int nodeValue, int position);
void print_list(struct Node *headNode);
void reverse_list(struct Node **headNode);


int main(void) {
  int i;
  struct Node *head = NULL;

  for(i = 1; i <= NUM_ITEMS; i++) {
    insert_node(&head, i, i);
  }
  print_list(head);

  printf("I will now reverse the linked list\n");
  reverse_list(&head);
  print_list(head);
  return 0;
}

void print_list(struct Node *headNode) {
  struct Node *iterator;

  for(iterator = headNode; iterator != NULL; iterator = iterator->next) {
    printf("Value: %d\n", iterator->data);
  }
}

void insert_node(struct Node **headNode, int nodeValue, int position) {
  int i;
  struct Node *currentNode = (struct Node *)malloc(sizeof(struct Node));
  struct Node *nodeBeforePosition = *headNode;

  currentNode->data = nodeValue;

  if(position == 1) {
    currentNode->next = *headNode;
    *headNode = currentNode;
    return;
  }

  for (i = 0; i < position - 2; i++) {
    nodeBeforePosition = nodeBeforePosition->next;
  }

  currentNode->next = nodeBeforePosition->next;
  nodeBeforePosition->next = currentNode;
}

void reverse_list(struct Node **headNode) {
  struct Node *iterator = *headNode;
  struct Node *previousNode = NULL;
  struct Node *nextNode = NULL;

  while (iterator != NULL) {
    nextNode = iterator->next;
    iterator->next = previousNode;
    previousNode = iterator;
    iterator = nextNode;
  }

  /* Iterator will be NULL by the end, so the last node will be stored in
  previousNode.  We will set the last node to be the headNode */
  *headNode = previousNode;
}

Spiegazione per il metodo dell'elenco inverso

Iniziamo il previousNode come NULL , dato che sappiamo sulla prima iterazione del ciclo, se stiamo cercando il nodo prima del primo nodo head, sarà NULL . Il primo nodo diventerà l'ultimo nodo nell'elenco, e la prossima variabile dovrebbe essere naturalmente NULL .

Fondamentalmente, il concetto di invertire la lista collegata qui è che in realtà invertiamo i collegamenti stessi. Il prossimo membro di ogni nodo diventerà il nodo prima di esso, in questo modo:

Head -> 1 -> 2 -> 3 -> 4 -> 5

Dove ogni numero rappresenta un nodo. Questa lista diventerebbe:

1 <- 2 <- 3 <- 4 <- 5 <- Head

Infine, la testa dovrebbe puntare al quinto nodo, e ogni nodo dovrebbe puntare al nodo precedente.

Il nodo 1 dovrebbe indicare NULL poiché non c'era niente prima. Il nodo 2 dovrebbe puntare al nodo 1, il nodo 3 dovrebbe puntare al nodo 2, eccetera.

Tuttavia, c'è un piccolo problema con questo metodo. Se interrompiamo il collegamento al nodo successivo e lo sostituiamo con il nodo precedente, non saremo in grado di passare al nodo successivo nell'elenco poiché il collegamento ad esso è scomparso.

La soluzione a questo problema è semplicemente memorizzare l'elemento successivo in una variabile ( nextNode ) prima di modificare il collegamento.

Una lista doppiamente collegata

Un esempio di codice che mostra come i nodi possono essere inseriti in una lista doppiamente collegata, come l'elenco può essere facilmente invertito e come può essere stampato al contrario.

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

/* This data is not always stored in a structure, but it is sometimes for ease of use */
struct Node {
  /* Sometimes a key is also stored and used in the functions */
  int data;
  struct Node* next;
  struct Node* previous;
};

void insert_at_beginning(struct Node **pheadNode, int value);
void insert_at_end(struct Node **pheadNode, int value);

void print_list(struct Node *headNode);
void print_list_backwards(struct Node *headNode);

void free_list(struct Node *headNode);

int main(void) {
  /* Sometimes in a doubly linked list the last node is also stored */
  struct Node *head = NULL;

  printf("Insert a node at the beginning of the list.\n");
  insert_at_beginning(&head, 5);
  print_list(head);

  printf("Insert a node at the beginning, and then print the list backwards\n");
  insert_at_beginning(&head, 10);
  print_list_backwards(head);

  printf("Insert a node at the end, and then print the list forwards.\n");

  insert_at_end(&head, 15);
  print_list(head);

  free_list(head);

  return 0;
}

void print_list_backwards(struct Node *headNode) {
  if (NULL == headNode)
  {
    return;
  }
  /*
  Iterate through the list, and once we get to the end, iterate backwards to print 
  out the items in reverse order (this is done with the pointer to the previous node).
  This can be done even more easily if a pointer to the last node is stored.
  */
  struct Node *i = headNode;
  while (i->next != NULL) {
    i = i->next; /* Move to the end of the list */
  }

  while (i != NULL) {
    printf("Value: %d\n", i->data);
    i = i->previous;
  }
}

void print_list(struct Node *headNode) {
  /* Iterate through the list and print out the data member of each node */
  struct Node *i;
  for (i = headNode; i != NULL; i = i->next) {
    printf("Value: %d\n", i->data);
  }
}

void insert_at_beginning(struct Node **pheadNode, int value) {
  struct Node *currentNode;

  if (NULL == pheadNode)
  {
    return;
  }
  /* 
  This is done similarly to how we insert a node at the beginning of a singly linked
  list, instead we set the previous member of the structure as well
  */
  currentNode = malloc(sizeof *currentNode);

  currentNode->next = NULL;
  currentNode->previous = NULL;
  currentNode->data = value;

  if (*pheadNode == NULL) { /* The list is empty */
    *pheadNode = currentNode;
    return;
  }

  currentNode->next = *pheadNode;
  (*pheadNode)->previous = currentNode;
  *pheadNode = currentNode;
}

void insert_at_end(struct Node **pheadNode, int value) {
  struct Node *currentNode;

  if (NULL == pheadNode)
  {
    return;
  }

  /*
  This can, again be done easily by being able to have the previous element.  It 
  would also be even more useful to have a pointer to the last node, which is commonly
  used.
  */
  
  currentNode = malloc(sizeof *currentNode);
  struct Node *i = *pheadNode;

  currentNode->data = value;
  currentNode->next = NULL;
  currentNode->previous = NULL;

  if (*pheadNode == NULL) {
    *pheadNode = currentNode;
    return;
  }

  while (i->next != NULL) { /* Go to the end of the list */
    i = i->next;
  }

  i->next = currentNode;
  currentNode->previous = i;
}

void free_list(struct Node *node) {
  while (node != NULL) {
    struct Node *next = node->next;
    free(node);
    node = next;
  }
}

Si noti che a volte è utile memorizzare un puntatore sull'ultimo nodo (è più efficiente essere semplicemente in grado di saltare direttamente alla fine dell'elenco piuttosto che dover eseguire un'iterazione fino alla fine):

struct Node *lastNode = NULL;

In tal caso, è necessario aggiornarlo in caso di modifiche all'elenco.

A volte, una chiave viene anche utilizzata per identificare gli elementi. È semplicemente un membro della struttura del nodo:

struct Node {
  int data;
  int key;
  struct Node* next;
  struct Node* previous;
};

La chiave viene quindi utilizzata quando qualsiasi attività viene eseguita su un elemento specifico, ad esempio l'eliminazione di elementi.