# 7.2.2 Basic Linked List Linked Lists are a common custom data structure. As the name implies, they are a list of **nodes** linked together. Each node has two basic parts, data and a link to the next node. Here is an example of a basic linked list that holds an integer. ![Source: By Lasindi - Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=2245162](https://codehs.com/uploads/ab4347ce4d64a51b48428670632ebfbc) Notice that each node has the two parts described above, an integer and a pointer to the next node. Starting at the head (first node) of the list, you can traverse through each value by tracing it through the linked node. One limitation though is that you cannot find an element in the middle. You must start at the head and traverse through the list. ### Linked List Implementation Implementing a linked list is the same concept regardless of what data the list will hold. In this example, you will have a chance to explore how linked lists are set up and traversed. **Head** - Each list must contain a head. The head is essentially how you access the list and is represented as the entry point for any list traversal. The head element is a pointer and it is initially pointing to a null pointer. **Inserting into the list** - To add nodes into the linked list, you follow a few basic steps: * Create a new node element and add the data to that element * Link the pointer in the new node element to point to the existing head * Update the head to point to the new node element. ### Example and Walkthrough Let’s create an example. In this example, the node element will be a struct: ``` struct item { int data; item *next; }; ``` The head item will be a pointer to an `item` and initially set to `NULL`. ``` item *head = NULL; ``` You can use a loop to populate data for this example. Inside the loop, you can see the 3 basic steps outlined above: Create the new node: ``` item *newItem = new item; newItem->data = newData; ``` Link the pointer of the new node to the existing head: ``` newItem->next = head; ``` Update the head item to point to the new node. ``` head = newItem; ``` Altogether, the loop looks like this: ``` for (int i = 0; i < 4; i++) { int newData = i; item *newItem = new item; newItem->data = newData; newItem->next = head; head = newItem; } ``` You can go review the walkthrough yourself here: {% embed url="" %} As the loop executes, you can see how the linked list is built. Partway through the loop, you will notice that `newItem` is created and points to an `item` object in the heap. Remember, att his point the `head` variable points to a `NULL` item. ![](https://codehs.com/uploads/25a61e5dd02d3f47e2b98062b47d4552) Once the first loop is complete, the `head` variable is updated to point to the new `item` that was just created and that new `item` next field now is `NULL` since it was updated from the `head` when it was `NULL`. This new item is esssentially the end of our list. Each item we add will be added before this item. ![](https://codehs.com/uploads/ed3532f02473e4a5463901964bbd9c00) As you progress in the second loop, you can see the next `item` getting created in the heap. The new data gets populated. ![](https://codehs.com/uploads/ccc36845754a0f8f35cd892ea5f13ac6) At the end of the second loop, notice how the `next` field of the new `item` has been updated to point to the old `head`, which was your first `item`. The `head` pointer has been updated to now point to the new `item`. ![](https://codehs.com/uploads/ee8470eaa164ad125c9c7dbedd405f91) Each loop, the process continues. A new `item` is created. The `next` field points to the old `head` and the `head` is then updated to point to the new `item`. ![](https://codehs.com/uploads/91192fc2af65e16a0ae52aae4f24acac) ### Traversing a Linked List To traverse a linked list you use a loop. Your only access point is the head element, so you start there, access the data, then access the next element. You can repeat until your next element is null, which is the end of the list, or the **tail**. Here is an example using the `item` node above: ``` item *nextItem = head; while(nextItem != NULL){ cout << nextItem->data << endl; nextItem = nextItem->next; } ``` Printing the data this way ends up being a Last-In, First-Out order like you see in a stack. What if you wanted to print it in a First-In, First-Out order like a queue? This is not easy to do using a while loop since you would want to start at the tail of the linked list and work backward, but the nodes don’t have any link to the previous element. ### [Try This Example](https://replit.com/@Poston/722-Basic-Linked-Lists#main.cpp) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mr-poston-1.gitbook.io/c++/7.-pointers-linked-lists-and-graphs/7.2-linked-lists/7.2.2-basic-linked-list.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.