{%hackmd @themes/orangeheart %}

# Data Structures - Linked Lists

Linked list is a linear data structure in which the elements are not stored in contiguous memory locations:


Linked list consists of nodes where each node has a data field and a reference(link) to the next node. **Data are linked using pointers.**

## The Concept and Implementation of Linked Lists

*Concept referenced to C Primer Plus - Chapter 17: Advanced Data Representation*

### Simple Linked Lists

We'll go over the example of a linked list using the concept of book reviews.

Suppose a user enters `The Greats` as a book title and gives it a rating of `5`:

#define SIZE 5
struct book{
    //members
    char title[SIZE];
    int rating;
    struct book *next; //next points to the next structure
};
struct book *head; 

- The program allocates memory for a `book` structure
- Copies the string `The Greats` into `title` members
- next member is pointed to `NULL`
- to indicate that **every structure is distinct and doesn't overlap**
- Points the first structure as `head`
- to **keep track** of where the first structure is stored

Now, the user enters another book with:

- title = `C Primer Plus`
- rating = `5`

The program allocates memory for a second `book` structure (overwriting the previous `NULL` address) so that the `next` pointer points to that structure in the linked list.

Each book review is handled the same way. New information goes into the new structure and it's next member is set to `NULL`, awaiting for the new member to be addressed in.

Displaying the list will have to track the head pointer.

### Implementation

## Linked List vs Arrays

### Fixed Sizes

Linked lists are used for several advantages compared to arrays. **For arrays, the size is fixed. This is to say that we must know the upper limit of the elements in the array in advance.**

### Insertion / Deletion

To add elements in an array, we have to shift all existing elements to a new position to insert a new element. This process is highly inefficient.

**Linked lists provide an easier way by traversing to any node and insert it at that position.**

As such, we need $O(n)$ time to insert a new element in arrays, whereas linked lists takes $O(1)$ time.

## Drawbacks

## Implementation of Linked Lists in C

### Doubly Linked Lists

### Circular Linked Lists