Section 5: Linked Lists

# Section 5

## Linked Lists

##### Presentation by *Asem Alaa*

<div class="my-header"><img src="/gallery/cairo.png" style="height: 30px;" /></div>
<div class="my-footer"><span>SBE201 Data Structures and Algorithms  (Spring 2020) - By <em>Asem Alaa</em></span></div>

---
class: left, top
## Linked Lists

#### Arrays vs. LL

* **Arrays** => **contiguous elements** in the memory. 
* **LL** => **sparse** in memory,

Each element in **LL** can see the *next* element.

#### Why linked lists

* .green[Very flexible in insertion/removal.]
* **Arrays** => .red[fixed sizes]
* **Arrays** => .red[expensive insertion]

---
### The Memory Mode: Array vs. Linked List

---
### Pointers revisited

* Each element => *node*. 
* To connect between nodes => **pointers**. 
* *node* has a **pointer** pointing to the *next node*.

---
### **DNA** sequence as a Linked List (LL)

```c++
struct node
{
    char data;
    node* next;
};
```

---
#### Linked list of doubles

```c++
struct node
{
    double data;
    node* next;
};
```

---
#### *Insert* element to the front:

```c++
node *pushFront( node *front , double data )
{
    front = new node{ data , front };
    return front;
}
```

##### Alternatively...

```c++
node *pushFront( node *front , double data )
{
    return new node{ data , front };
}
```

---
#### *Insert* element to the back

```c++
node *pushBack( node *front, double data )
{
    if( front == nullptr )
    {
        front = new node{ data , front };
        return front;
    }
    else
    {
        node *temp = front;
        while( temp->next != nullptr )
            temp = temp->next;
        temp->next = new node{ data , nullptr };
        return front;
    }
}
```

---
#### *Insert* element to the back (+DRY)

```c++
node *pushBack( node *front, double data )
{
    if( front == nullptr )
        return pushFront( front , data );
    else
    {
        node *temp = front;
        while( temp->next != nullptr )
            temp = temp->next;
        temp->next = new node{ data , nullptr };
        return front;
    }
}
```

---
#### The last node (back)

```c++
node *backNode( node *front )
{
    node *temp = front;
    while( temp->next != nullptr )
        temp = temp->next;
    return temp;
}
```

---
class: small
#### *Insert* element to the back (+DRY)

```c++
node *backNode( node *front )
{
    node *temp = front;
    while( temp->next != nullptr )
        temp = temp->next;
    return temp;
}

node *pushBack( node *front, double data )
{
    if( front == nullptr )
        return pushFront( front , data );
    else
    {
        node *temp = front;
        while( temp->next != nullptr )
            temp = temp->next;
        temp->next = new node{ data , nullptr };
        return front;
    }
}
```

---
class: small
#### *Insert* element to the back (++DRY)

```c++
node *backNode( node *front )
{
    node *temp = front;
    while( temp->next != nullptr )
        temp = temp->next;
    return temp;
}

node *pushBack( node *front, double data )
{
    if( front == nullptr )
        return pushFront( front , data );
    else
    {
        node *back = backNode( front );
        back->next = new node{ data , nullptr };
        return front;
    }
}
```

---
#### Linked list in main function

```c++
#include <iostream>
struct node
{
    double data;
    node* next;
};
node *pushFront( node *front , double data ){ ... }
node *backNode( node *front ){ ... }
node *pushBack( node *front, double data ){ ... }
int main()
{
    node* l = nullptr; // Empty list
    // append elements with values 1^2 to 10^2
    for (int i=1; i<=10; ++i)
        l = pushBack( l , i*i);
    // print all elements followed by a space
    for (node *temp = l; temp != nullptr; temp = temp->next )
        std::cout << temp->data << ' ';
}
```

---
#### Linked list traversal

```c++
void printLL( node* front )
{
    node *current = front;
    while( current != nullptr )
    {
        std::cout << current->data;
        current = current->next;
    }
}
```