C Language
Połączone listy

Uwagi

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);
}

Wstawienie węzła na początku pojedynczo połączonej listy

Poniższy kod wyświetli monit o podanie liczb i będzie nadal dodawał je na początku listy połączonej.

/* 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;
}

Wyjaśnienie dotyczące wstawiania węzłów

Aby zrozumieć, jak dodajemy węzły na początku, spójrzmy na możliwe scenariusze:

1. Lista jest pusta, dlatego musimy dodać nowy węzeł. W takim przypadku nasza pamięć wygląda tak, gdzie HEAD jest wskaźnikiem do pierwszego węzła:

| HEAD | --> NULL

Linia currentNode->next = *headNode; przypisze wartość currentNode->next NULL ponieważ headNode początkowo zaczyna się od wartości NULL .

Teraz chcemy ustawić wskaźnik głównego węzła, aby wskazywał na nasz bieżący węzeł.

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

Odbywa się to za pomocą *headNode = currentNode;

2. Lista jest już zapełniona; musimy dodać nowy węzeł na początku. Dla uproszczenia zacznijmy od 1 węzła:

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

W przypadku currentNode->next = *headNode struktura danych wygląda następująco:

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

Co oczywiście należy zmienić, ponieważ *headNode powinien wskazywać na currentNode .

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

Odbywa się to za pomocą *headNode = currentNode;

Wstawienie węzła w n-tej pozycji

Do tej pory zastanawialiśmy się nad wstawieniem węzła na początku pojedynczo połączonej listy . Jednak przez większość czasu będziesz mógł wstawiać węzły również w innym miejscu. Poniższy kod pokazuje, jak można napisać funkcję insert() celu wstawienia węzłów w dowolne miejsce na połączonych listach.

#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;
  }
}

Odwracanie połączonej listy

Możesz również wykonać to zadanie rekurencyjnie, ale w tym przykładzie wybrałem iteracyjne podejście. To zadanie jest przydatne, jeśli wstawiasz wszystkie węzły na początku listy połączonej . Oto przykład:

#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;
}

Objaśnienie metody odwróconej listy

Zaczynamy previousNode jako NULL , ponieważ wiemy przy pierwszej iteracji pętli, jeśli szukamy węzła przed pierwszym węzłem głównym, będzie to NULL . Pierwszy węzeł stanie się ostatnim węzłem na liście, a następna zmienna powinna oczywiście mieć NULL .

Zasadniczo koncepcja odwrócenia połączonej listy polega na tym, że faktycznie odwracamy same łącza. Następny element każdego węzła stanie się węzłem przed nim, w ten sposób:

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

Gdzie każda liczba reprezentuje węzeł. Ta lista stałaby się:

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

Wreszcie głowa powinna zamiast tego wskazywać na 5. węzeł, a każdy węzeł powinien wskazywać na poprzedni węzeł.

Węzeł 1 powinien wskazywać NULL ponieważ nic przed nim nie było. Węzeł 2 powinien wskazywać na węzeł 1, węzeł 3 powinien wskazywać na węzeł 2 i tak dalej.

Istnieje jednak jeden mały problem z tą metodą. Jeśli zerwamy łącze do następnego węzła i zmienimy go na poprzedni, nie będziemy mogli przejść do następnego węzła na liście, ponieważ łącze do niego zniknęło.

Rozwiązaniem tego problemu jest po prostu przechowywanie następnego elementu w zmiennej ( nextNode ) przed zmianą łącza.

Podwójnie połączona lista

Przykład kodu pokazującego, w jaki sposób węzły można wstawiać na podwójnie połączonej liście, jak łatwo można odwrócić listę i jak można ją wydrukować w odwrotnej kolejności.

#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;
  }
}

Zauważ, że czasami przechowywanie wskaźnika do ostatniego węzła jest przydatne (bardziej wydajne jest po prostu przeskakiwanie od razu do końca listy niż konieczność iteracji do końca):

struct Node *lastNode = NULL;

W takim przypadku konieczna jest aktualizacja po zmianie listy.

Czasami klucz służy również do identyfikacji elementów. Jest to po prostu element struktury węzła:

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

Klucz jest następnie używany, gdy jakiekolwiek zadania są wykonywane na określonym elemencie, np. Usuwanie elementów.