Data Structures: Linked Lists
This is my first blog in a series where I will be looking at different data structures used in programming.
What is a Linked List
A linked list is a linear data structure comprised of individual nodes. Each of these nodes is contains two elements: a piece of data and a pointer reference to the memory address of the next node in the list. Thanks to this pointer, nodes in a linked list do not need to be stored in consecutive memory addresses, but can be placed anywhere in the computer’s memory and still keep their linear structure.

Structure of a Linked List
The first node in a linked list is called the head, it will be where any searches or iterations of the linked list will start. The last node is called the tail, the next pointer of the tail points to a null value and is used to signify the end of the linked list to any methods called on it. Between the head and the tail can be any number of nodes that create the rest of the list.

Advantages and Disadvantages of Linked Lists
The biggest advantage of using a linked list comes from the ease of inserting and deleting elements from it. The use of pointers to connect the nodes also allows you to add elements without having to allocate large blocks of consecutive memory like you would for a an array. The biggest disadvantage to using a linked list is the inability to directly access individual nodes, instead you must iterate through the entire list until you find the specific node you are looking for.
Creating a Linked List
struct LinkedList{
int data;
struct LinkedList *next;
};This is the structure of each node in our linked list. It contains a piece of data and a pointer to the next node.
typedef struct LinkedList *node;
node createNode(){
node temp;
temp = (node)malloc(sizeof(struct LinkedList));
temp->next = NULL;
return temp;
}Next we will create a node as a pointer of data type struct LinkedList. We use malloc to allocate the memory needed for the node. Set the next to point to NULL. Finally we will return the newly created node.
Adding to a Linked List
node addNode(node head, int value){
node toInsert,currentNode;
toInsert = createNode();
toInsert->data = value;
if(head == NULL){
head = toInsert;
}
else{
currentNode = head;
while(currentNode->next != NULL){
currentNode = currentNode->next;
}
currentNode->next = toInsert;
}
return head;
}Adding a new node to the end of a linked list. First we will create two new nodes the first node will be the one that contains our data and we will be inserting into our list; the second node will keep track of the other nodes as we iterate through the list.
We can first check and see if there is already a head node, if not than our toInsert node will be the start of the new list. if a head node exists we will set our currentNode to the head and begin iterating through the list. When our currentNode reaches a the point where it points to NULL instead of to another node we will know we are at the end of the list.
From here we simply change the pointer of the last node to point to our node that we are inserting into the list.

A similar function structure can be used to insert new nodes anywhere in the list and not just at the end. Along with tracking our current node also need to track the previous node of the iteration. To insert a new node between the current and previous nodes we simply change the previous node to point to our new node and our new node to point to the current node.