Tossaporn Saengja

Linked List

คำอธิบาย

https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg

Singly Linked List

ตัวอย่างการ implement singly linked list

// A simple CPP program to introduce
// a linked list
#include <bits/stdc++.h>
using namespace std;

// A linked list node
struct Node {
  int data;
  struct Node *next;
};

int main() {
  // Program to create a simple linked
  // list with 3 nodes
  Node *head = NULL;
  Node *second = NULL;
  Node *third = NULL;

  // allocate 3 nodes in the heap
  head = new Node();
  second = new Node();
  third = new Node();

  /* Three blocks have been allocated dynamically.
     We have pointers to these three blocks as head,
     second and third
     head         second         third
     |             |             |
     |             |             |
     +----+----+   +----+----+   +----+----+
     | #  |  # |   | #  | #  |   | #  | #  |
     +----+----+   +----+----+   +----+----+

  # represents any random value.
  Data is random because we haven’t assigned
  anything yet */

  head->data = 1;      // assign data in first node
  head->next = second; // Link first node with
  // the second node

  /* data has been assigned to the data part of first
     block (block pointed by the head). And next
     pointer of the first block points to second.
     So they both are linked.

     head         second         third
     |             |             |
     |             |             |
     +---+---+     +----+----+   +-----+----+
     | 1 | o-----> | #  | #  |   | #   | #  |
     +---+---+     +----+----+   +-----+----+
   */

  // assign data to second node
  second->data = 2;

  // Link second node with the third node
  second->next = third;

  /* data has been assigned to the data part of the second
     block (block pointed by second). And next
     pointer of the second block points to the third
     block. So all three blocks are linked.

     head         second         third
     |             |             |
     |             |             |
     +---+---+     +---+---+     +----+----+
     | 1 | o-----> | 2 | o-----> | #  | #  |
     +---+---+     +---+---+     +----+----+     */

  third->data = 3; // assign data to third node
  third->next = NULL;

  /* data has been assigned to the data part of the third
     block (block pointed by third). And next pointer
     of the third block is made NULL to indicate
     that the linked list is terminated here.

     We have the linked list ready.

     head
     |
     |
     +---+---+     +---+---+     +----+------+
     | 1 | o-----> | 2 | o-----> | 3  | NULL |
     +---+---+     +---+---+     +----+------+

     Note that only the head is sufficient to represent
     the whole list. We can traverse the complete
     list by following the next pointers. */

  while (head != NULL) {
    printf("%d ", head->data);
    head = head->next;
  }

  // This code is contributed by rathbhupendra
}

Operations

https://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/CPT-LinkedLists-addingnode.svg/474px-CPT-LinkedLists-addingnode.svg.png

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/CPT-LinkedLists-deletingnode.svg/380px-CPT-LinkedLists-deletingnode.svg.png

Doubly Linked List

https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/610px-Doubly-linked-list.svg.png

// linked.c
#include <bits/stdc++.h>
using namespace std;

// what a node look like internally
struct Node {
  int idx;
  struct Node *r_next;
  struct Node *r_prev;
};

int main() {
  // define 3 nodes
  struct Node n0, n1, n2;

  // initialize the nodes
  n0.idx = 0;       // the first node has an index of 0
  n0.r_next = &n1;  // with a reference to the second node
  n0.r_prev = NULL; // and a reference to NULL b/c there's no previous node

  n1.idx = 1;
  n1.r_next = &n2;
  n1.r_prev = &n0;

  n2.idx = 2;
  n2.r_next = NULL;
  n2.r_prev = &n1;

  // create a new reference to n0 called r_first_element
  struct Node *r_first_element = &n0;
  printf("The first node lives @ %p\n", r_first_element);
  printf("The first node has idx: %d\n", r_first_element->idx);

  // print n1 info
  printf("The second node lives @ %p\n", r_first_element->r_next);
  printf("The second node has idx: %d\n", r_first_element->r_next->idx);

  // print n2 info
  printf("The third node lives @ %p\n", r_first_element->r_next->r_next);
  printf("The third node has idx: %d\n", r_first_element->r_next->r_next->idx);
}