C Language
연결된 목록

비고

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

단일 연결 목록 시작 부분에 노드 삽입

아래 코드는 숫자를 묻는 메시지를 표시하고 연결된 목록의 시작 부분에 계속 추가합니다.

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

노드 삽입에 대한 설명

처음에 노드를 추가하는 방법을 이해하기 위해 가능한 시나리오를 살펴 보겠습니다.

1. 목록이 비어 있으므로 새 노드를 추가해야합니다. 이 경우 HEAD 가 첫 번째 노드에 대한 포인터 인 경우 다음과 같이 표시됩니다.

| HEAD | --> NULL

line currentNode->next = *headNode; 의 값을 할당합니다 currentNode->next 가 될 NULL 하기 때문에 headNode 원래의 값으로 밖으로 시작 NULL .

이제 머리 노드 포인터를 현재 노드를 가리 키도록 설정하려고합니다.

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

이것은 *headNode = currentNode;

2. 목록에 이미 채워져 있습니다. 우리는 처음에 새로운 노드를 추가해야합니다. 간단히하기 위해 1 노드부터 시작합시다.

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

currentNode->next = *headNode 를 사용하면 데이터 구조는 다음과 같습니다.

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

*headNode 가 currentNode 가리켜 야하기 때문에 분명히 변경되어야합니다.

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

이것은 *headNode = currentNode;

n 번째 위치에 노드 삽입

지금까지 단일 링크 목록의 시작 부분에 노드를 삽입하는 방법 을 살펴 보았습니다. 그러나 대부분의 경우 다른 곳에 노드를 삽입 할 수 있기를 원할 것입니다. 아래 작성된 코드는이 작성할 수 있습니다 방법을 보여줍니다 insert() 링크 된 목록에 어디 노드를 삽입하는 기능.

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

연결된 목록 반전

이 태스크를 재귀 적으로 수행 할 수도 있지만 반복적 인 접근 방식을 사용하기 위해이 예제에서 선택했습니다. 이 작업은 연결된 목록의 시작 부분에 모든 노드를 삽입 할 때 유용 합니다 . 다음은 그 예입니다.

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

역방향 목록 메서드에 대한 설명

우리는 루프의 첫 번째 반복을 알기 때문에 previousNode 를 NULL 로 시작합니다. 첫 번째 헤드 노드 전에 노드를 찾고 있다면 NULL 이 NULL . 첫 번째 노드는 목록의 마지막 노드가되고 다음 변수는 당연히 NULL 이어야 NULL .

기본적으로 링크 된 목록을 역전시키는 개념은 실제로 링크 자체를 역으로 처리한다는 것입니다. 각 노드의 다음 멤버는 이전 노드가됩니다.

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

여기서 각 숫자는 노드를 나타냅니다. 이 목록은 다음과 같이됩니다.

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

마지막으로 머리는 다섯 번째 노드를 가리켜 야하며 각 노드는 이전 노드를 가리켜 야합니다.

노드 1은 앞에 아무 것도 없기 때문에 NULL 가리켜 야합니다. 노드 2는 노드 1을 가리키고, 노드 3은 노드 2를 가리켜 야합니다.

그러나이 방법에는 하나의 작은 문제 가 있습니다. 다음 노드로의 링크를 끊고 이전 노드로 변경하면 링크가 사라져서 목록의 다음 노드로 넘어갈 수 없습니다.

이 문제에 대한 해결책은 링크를 변경하기 전에 다음 요소를 변수 ( nextNode )에 저장하는 것입니다.

이중 연결된 목록

이중 연결된 목록에 노드를 삽입하는 방법, 목록을 쉽게 되돌릴 수있는 방법 및 역순으로 인쇄 할 수있는 방법을 보여주는 코드의 예입니다.

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

마지막 노드에 대한 포인터를 저장하는 것이 유용 할 때가 있습니다 (끝까지 반복 할 필요없이 목록의 끝으로 곧바로 이동할 수있는 것이 더 효율적입니다).

struct Node *lastNode = NULL;

어떤 경우에는 목록을 변경하면 업데이트해야합니다.

키를 사용하여 요소를 식별하는 경우도 있습니다. 이것은 단순히 Node 구조의 멤버입니다.

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

그런 다음 요소 삭제와 같은 특정 요소에서 작업이 수행 될 때 키가 사용됩니다.