> For the complete documentation index, see [llms.txt](https://stephanosterburg.gitbook.io/scrapbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://stephanosterburg.gitbook.io/scrapbook/coding/coding-interview/data-structures/linked-list.md). # Linked List **Interview Essentials** A linked list is a sequential-access data structure used for storing *ordered* elements. They prioritize quick and easy data insertion and deletion over item lookup. All linked lists are collections of `node` data structures that are connected by `pointers` - that's where the "link" in "linked list" comes from. Linked list questions are short and simple for an interviewer to ask, but they have complex solutions that really show off your problem-solving and coding skills. This means that they’re very common in technical interviews, so it’s important to be comfortable with using this data structure. You’ll use linked lists to solve questions in which having quick insertion and deletion is important, and when it’s not important to be able to have random access to elements. **Types of Linked Lists** We primarily see two types of linked lists: * **Singly linked list:** (most common)\ Each node contains the `data` we want to store, as well as a `next` pointer to the next node in the linked list. Singly linked lists support traversal in only one direction. \ \&#xNAN;*Common interview question:* Find a way to access earlier information in the list. * **Doubly linked list:**\ Each node contains the `data` we want to store, as well as `next` and `previous` pointers to the node's neighboring elements. Doubly linked lists support traversal in both directions. \ \&#xNAN;*Common interview question:* Implement a linked list. Doubly linked lists require more space per node and their basic operations are more expensive than for singly linked lists. However, they are often easier to manipulate than singly linked lists because they allow for fast and easy sequential access to the list in both directions. **Essential Vocab** * **Pointer:** The memory location of a data structure. * **Node:** A data structure with two fields. The `data` field contains the information we want to store, and the `next` field, which is a pointer to the next node in the linked list. A linked list can be thought of as a series of nodes. Nodes for doubly linked lists need `next` and `previous` pointers. ![A node for a singly-linked list and a doubly-linked list](https://codefightsuserpics.s3.amazonaws.com/tutorials/linked-lists/node_example.png) A *node* for a singly linked list and a doubly linked list * **Head:** A pointer to the first node in the linked list. All nodes are accessible from the head node by visiting the chain of previous nodes. * **Tail:** The last element in the linked list. The \`next\` pointer of the tail element points to \`null\` to indicate the end of the list. * **Size:** The number of elements in the linked list. ![](/files/-LcSLFEzNNPGG-xvpFHF) A singly linked list with a *size* of 4 **Strengths & Weaknesses** Linked lists are often compared to arrays, a data structure that provides random access to elements, meaning that their strengths and weaknesses are frequently compared to those of arrays as well. **Strengths** * Linked lists store ordered lists of data in nodes. * Linked lists allow for quick (`O(1)`) addition and removal of elements (advantage over an array). * Linked lists can be resized dynamically. * The size of a linked list is only limited by the amount of available memory. **Weaknesses** * Linked lists can require more space in memory than arrays do. * Linked lists are sequential-access instead of random-access, meaning that accessing the `ith` element can be slow because you must iterate over `i` elements to get there. **In Interviews, Use a Linked List When...** * You don't know the number of elements in your list before you start. * You have lists that need to grow (e.g. accepting input from files, the internet, other streams, etc.) * You need to implement a more sophisticated data structure like a heap, stack, or queue. **Common Operations Cheat Sheet** | Operation | Description | Time complexity | Mutates structure | | ---------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------- | ----------------- | | `find(value)` | Returns a pointer to the `node` containing `value` in the data field, or NULL if it isn't in the list. This method can be used for `membership checking` as well. | *O(N)* | No | | `find(index)` | Returns a pointer to the `index`th node from the head pointer, or NULL if `index` is longer than the length of the list. | *O(index)* | No | | `addBeginning(value)` | Adds a new node with a data field containing `value` to the beginning of the list | *O(1)* | Yes | | `addAfter(value, n)` | Adds a new node with a data field containing `value` after node `n` | *O(1)* | Yes | | `remove(value)` | Removes first instance of value from list | *O(N)* if we need to find the element. | Yes | | `removeNextElement(n)` | Removes node after `n` | *O(1)* | Yes | | `removeThisElement(n)` | Removes node `n` | *O(1)* on doubly linked-list | Yes | --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## 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, and the optional `goal` query parameter: ``` GET https://stephanosterburg.gitbook.io/scrapbook/coding/coding-interview/data-structures/linked-list.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. 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.