# Project: Linked Lists

## Introduction

In our previous lesson, we looked at `Nodes`, `Linked Lists` and `Trees`; the latter two being core `data structures` to add to your repetoire, and `Nodes` being the foundation those `data structures` are built upon.

As stated previously, if your language of choice is `Ruby` or `JavaScript`, in practice you won't have to concern yourself with implementing `Linked Lists` as `Arrays` are not a fixed sized in these languages. However, learning how `Nodes` work by writing them, and building a `Linked List` with them; will give you a working understanding of how `Linked Lists` work, and give you a solid, founding principle for tackling the bigger task ahead...

`Trees.`

## Structure of a Linked List

A *linked list* is a linear collection of data elements called nodes that "point" to the next node by means of a pointer.

Each node holds a single element of data and a link or pointer to the next node in the list.

A head node is the first node in the list, a tail node is the last node in the list. Below is a basic representation of a linked list:

`[ NODE(head) ] -> [ NODE ] -> [ NODE(tail) ] -> nil`

For a more thorough explanation, use these resources:

1. [Linked Lists in Plain English](https://www.youtube.com/watch?v=oiW79L8VYXk)
2. [Linked Lists, Ruby's Missing Data Structure](https://www.sitepoint.com/rubys-missing-data-structure/)
3. [A more verbose explanation with plenty of diagrams](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html)

## Assignment

In your language of choice...

You will need two classes:

1. `LinkedList` class, which will represent the full list.
2. `Node` class, containing a `#value` method and a link to the `#next_node`, set both as `nil` by default.

Build the following methods in your linked list class:

1. `#append(value)` adds a new node containing `value` to the end of the list
2. `#prepend(value)` adds a new node containing `value` to the start of the list
3. `#size` returns the total number of nodes in the list
4. `#head` returns the first node in the list
5. `#tail` returns the last node in the list
6. `#at(index)` returns the node at the given `index`
7. `#pop` removes the last element from the list
8. `#contains?(value)` returns true if the passed in value is in the list and otherwise returns false.
9. `#find(value)` returns the index of the node containing value, or nil if not found.
10. `#to_s` represent your LinkedList objects as strings, so you can print them out and preview them in the console.

    The format should be: `( value ) -> ( value ) -> ( value ) -> nil`

## Extra credit

1. `#insert_at(value, index)` that inserts the node with the provided `value` at the given `index`
2. `#remove_at(index)` that removes the node at the given `index`. (You will need to update the links of your nodes in the list when you remove a node.)


---

# 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://howtocode.trek.io/topics/deep-dives/computer-science/data-structures/project-linked-lists.md?ask=<question>
```

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.