Linked list

In previous weeks we discussed about:

• the superpower of struct’s before in section Self-referential struct, where we built an infinite string.

• Static- and stack-based memory

  • we will introduce heap-based memory

Definition

linked list

a linear collection of data elements whose order is not given by their physical placement in memory.

(singly) linked list

Fig. 27 A linked list. Each node contains data (e.g., 12) and a pointer to the next node. ☒ stands for nullptr.
Public domain. By Vectorization: Lasindi. Source: Wikimedia Commons

doubly linked list

Fig. 28 Doubly linked list
Public domain. By Lasindi. Source: Wikimedia Commons

Activity 62 (Implementing a singly linked list)

Implement a linked list similar . Milestones:

1. Create a struct that contains an integer and a self-reference.

2. Declare a pointer called head, which will point to the first element

3. Implement a function insert TODO

Activity 63 (Appropriate data structure for FrankenText)

In FrankenText we used many arrays.

1. Write down arrays and their sizes. A pointer and size_t have 8 byte each.

2. How do these sizes affect the performance of our program or even other programs?

3. How could we reduce the memory used by our program?

   Hint

   • Could Sequential IO with stdin & stdout help?

Array vs linked list

Fig. 29 Visualization of appending the letter W to an array (names as list above) and linked list.
CC BY-SA 4.0. By Mathreturn. Source: Wikimedia Commons

Array elements are always in sequence and its space cannot be changed after declaration. See Fig. 29.

1. Above (list): If we wanted to add additional data and array does not have reserved a space for additional data, we have to allocate larger space and copy the original array and additional data to the larger space

2. Below (linked list): In contrast, we don’t have to copy the original data, but (1) allocate new space for the new data and (2) connect the new data to the original data.

Insert operation on a linked list

Fig. 30 newNode is inserted after node A in a double linked list.
Public domain. By Vectorization: Alhadis. Source: Wikimedia Commons

For modification, we need the following steps:

1. Find the node we want to insert the element after.

2. Allocate new space for newNode using malloc on the heap memory

3. Link newNode with the neighboring nodes

Heap-based memory

typedef struct S S;

S *f1() {
   S s;
  // stack-based memory 
  // Released after the function returns.
  //...
  return &s;  // ❌ will be overwritten by other functions
}

S *f2() {
    S *sp = (S*)malloc(sizeof(S));
    // heap-based memory
    // Persists after the function returns.
    //...
    return sp;
}
auto sp = f2();
//...
free(sp);
// Deallocates sp.
// In other words, gives the memory area free for other users.