Recap of Arrays
Recall arrays are always of a fixed size, you declare them and then access them by their index. This is fast and efficient to get an array if you have have static data of a fixed size.
Unforunately there are some problems, while you can add to an array through weird means it's not normally what they are used for.
This causes people to define arrays bigger than they actually need to anticipate there memory usage, this either ends in wasting memory or segfaulting when you run out.
Also seemengly simple operations on arrays become big tasks like if you wanted to delete an element from an array.
Sounds simple right but there is no real way to do so without makeing a copy of the entire thing and filling in a new one omitting the item in question, not efficint for a large array.
Or prehaps you wanted to put in an item at the begining of the array pushing all the rest of the elements back a spot?
Again hard and requires copying of large chunks of info.
Linked Lists
In almost every way where arrays are weak linked lists are strong and vice versa.
- Linked lists are dynamically allocated only makeing a new element when needed, and have simple operations for functions like pushing, poping and deleting elements.
- Just by changing one pointer in a linked list, complex array operations can be preformed.
- But it does have downsides, if you know the location of an element the access time for a simple linked lists is O(n) insead of O(1).
- If you explicitly said x[n] that would be an O(1) operation for an array but for a linked list it would have to iterate n times making it O(n).
- Also because of their dynamic nature the designer has to free and allocate the new memory themselves.
How do we define a linked list?
typedef struct node {
struct node* next;
} node;
And it's as simple as that. All a liked list is, is a series of nodes connected by a pointer to the next one in the list.
But obviously we probably want some data in there so let's define some stuff.
typedef struct node {
char name[20];
int age;
struct node* next;
} node;
How do we create linked list?
The idea behind linked lists is that you never directly have access to the whole thing at one time. What you do keep constant track of is top or head of the list.
If you lose this pointer to the head of the list the entire list is gone, so usually the head is stored in main and pass around or minipulated.
A NULL list is just and empty linked list.
So to create a new linked list just initialize a new node pointer to NULL.
node* head = NULL;
Now everything will be added to this new head pointer.
Note you do need to initialize the head to NULL just like variables because it will explicitly give all pointers a ligit memory location but is one that has not memory so it will be a segfalut.
How do we insert into a linked list?
Inserting new nodes is simple, just allocate the memory needed for your node struct, set your data, and set the next pointer to the current head.
- Allocate the memory needed for a new node struct.
- Set your new data into this struct
- Set the pointer of the newly created node to the head of the list.
This is why it is much easier to insert nodes at the begining of a list rather than the end because you always start at the head.
This is known as a "Push" because your new node pushed every other node back a space.
How do we iterate through linked list?