Linked Lists

• Thus far, only arrays have provided us a means of representing a collection of like values.

​

• They are great for element lookup, but pretty terrible for inserting unless we happen to be tacking on to the end of an array.

​

• Arrays are also quite inflexible; what happens if we need a larger array than we thought? With clever use of structs and pointers - maybe there’s a fix!

• We refer to this combination of structs and pointers, when used to create a “chain” of nodes a linked list.

​

• A linked list node is a special type of struct with two fields:
• Data of some type
• A pointer to another linked list node.

typedef struct node

{

int value;

struct node *next;

}

node;

• In order to work with linked lists effectively, there are five key operations to understand (only the first four of which are really needed in this course):
• Creating a linked list when it doesn’t exist.
• Searching through a linked list to find an element.
• Inserting a new node into a linked list.
• Deleting an entire linked list.
• Deleting a single element from a linked list.

• Create a linked list:
• Dynamically allocate space for a new (your first!) node.
• Check to make sure you didn’t run out of memory.
• Initialize the value field.
• Initialize the next field (specifically, to NULL).
• Return a pointer to your newly created node.

• Create a linked list:
• Dynamically allocate space for a new (your first!) node.
• Check to make sure you didn’t run out of memory.
• Initialize the value field.
• Initialize the next field (specifically, to NULL).
• Return a pointer to your newly created node.

• Create a linked list:
• Dynamically allocate space for a new (your first!) node.
• Check to make sure you didn’t run out of memory.
• Initialize the value field.
• Initialize the next field (specifically, to NULL).
• Return a pointer to your newly created node.

• Create a linked list:
• Dynamically allocate space for a new (your first!) node.
• Check to make sure you didn’t run out of memory.
• Initialize the value field.
• Initialize the next field (specifically, to NULL).
• Return a pointer to your newly created node.

• Create a linked list:
• Dynamically allocate space for a new (your first!) node.
• Check to make sure you didn’t run out of memory.
• Initialize the value field.
• Initialize the next field (specifically, to NULL).
• Return a pointer to your newly created node.

new

• Find an element:
• Create a traversal pointer pointing to the list’s head (first element).
• If the current node’s value field is what we’re looking for, return true.
• If not, set the traversal pointer to the next pointer in the list and go back to the previous step.
• If you’ve reached the element of the list, return false.

• Insert an element:
• Dynamically allocate space for a new linked list node.
• Check to make sure we didn’t run out of memory.
• Populate and insert the node at the beginning of the linked list.
• Return a pointer to the new head of the linked list.

• Insert an element:
• Dynamically allocate space for a new linked list node.
• Check to make sure we didn’t run out of memory.
• Populate and insert the node at the beginning of the linked list.
• So which pointer do we move first? The pointer in the newly created node, or the pointer pointing to the original head of the linked list?
• This choice matters!
• Return a pointer to the new head of the linked list.

list

new

list

new

list

new

X

list

new

list

new

list

new

✔

• Delete an entire linked list:
• If you’ve reached a NULL pointer, stop.
• Delete the rest of the list.
• Free the current node.

​

• Sounds like recursion!