Instantly share code, notes, and snippets.

Last active January 15, 2018 22:41

Linked lists are a way to store sequential data. A linked list is made up of one or more list nodes that contain the data and a link or pointer to the next node in the sequence. We call the start of the linked list the head and the end of the linked list the tail. ### Why would we use a linked list?

• Constant time insertions/deletions
• Easily expandable

### Constant time Insertions/Deletions:

Let’s think about how data is stored on our computers. When using an array the items in our array are stored one after another in memory in contiguous blocks something like this:

Register Stored Data Register Stored Data
Loc # 608 “Chicago” Loc # 608 “Atlanta”
Loc # 609 “Columbus” Loc # 609 “Chicago”
Loc # 610 “Denver” Loc # 610 “Columbus”
Loc # 611 “Kansas City” Loc # 611 “Denver”
Loc # 612 “New York” Loc # 612 “Kansas City”
Loc # 613 Loc # 613 “New York”

Here we have an array with 5 items with space for 1 additional item. Array is “Chicago” and array is “New York”. Great! But what happens if we wanted to add “Atlanta” to the first spot in our list? Each item in our array would need to be shifted one spot down to make room for “Atlanta” and that could take a while if we had a really big array.

Linked lists aren’t stored in contiguous blocks of memory, so when a node is added to the list the location of the other nodes isn’t affected. To add a node we just need to update a link or two, and this can be done with the same number of steps each time. For example:

If you’re familiar with big O notation, we’d say that removing or inserting a value at the front of an array is O(n). For a linked list though removing or inserting a value at the front of the list is O(1), or constant time. For some applications this could be very useful!

### Easily Expandable:

Let’s think back to our previous array. It was only allocated 6 blocks in memory. What happens if we wanted to add “Los Angeles” to it?

Register Stored Data
Loc # 608 “Atlanta”
Loc # 609 “Chicago”
Loc # 610 “Columbus”
Loc # 611 “Denver”
Loc # 612 “Kansas City”
Loc # 613 “New York”

Since the array is full, the system would need to find a new location for a bigger array, copy over all the items in the array, and then add the new item. With a linked list though, we’d just have to add another node - since it doesn’t need contiguous blocks of memory it’s very flexible.

### Why wouldn’t we use a linked list?

Linked lists aren’t as easy to navigate. Arrays have a special property - you can access any item in the linked list in constant time. If we wanted the second item in our array we could use array. But with linked lists we have to start at the head node and follow the next links until we get to the item we want. For example:

In big O notation we’d say an array has O(1) or constant time access, but linked lists have O(n) access because we may need to traverse every node in the linked list to get to the node we want.

### Are there other types of linked lists?

Three common types:

• Singly linked lists (this is what we’ve been using!)
• Doubly linked lists - has link to the next node AND the previous node
• Circular linked lists - the next value of the last node is the head

### How do we use a linked list?

Here is a definition for a list node and a linked list in Python.

```class ListNode:
def __init__(self, val=None):
self.data = val
self.next = None
def __init__(self):

We can create the head of our list like this:

```my_list = LinkedList()
node = ListNode(10)

Let’s create a method to insert a node at the end of a Linked List!

```def insertAtEnd(self, data):
node = ListNode(data)
else:
while curr.next is not None:
curr = curr.next
curr.next = node```

### Even or Odd?

Given a Singly Linked-List, check whether its length is even or odd.

Example:

``````1->2->3->4 ==> True
1->2->3->4->5 ==> False
``````

Hint # 1: Traversing over the linked list with 2x the speed (over two nodes at a time) in a loop can give you an interesting and efficient solution in a single pass.

Hint # 2:

1. Traverse over the `Linked List` by hopping over two `Nodes` at a time.
2. While traversing, keep a check to exit out of the loop if the `next` reference of the `current Node` becomes `None`.
3. If the `current Node` becomes `None` at the end of the traversal, the length is even - otherwise it's odd.
```   def is_list_even(self):
c = 1
while n.next:
n = n.next
c += 1
return c % 2 == 0
return True
OR:  def is_list_even(self):
while current is not None:
if current.next is not None:
current = current.next.next
else:
break
if current is None:
return True
else:
return False```

### Reverse a Singly Linked List **

Given a singly linked list, write a method to perform In-place reversal.

Example:

``````1->2->3 ==> 3->2->1
``````

Hint # 1: The key here is to reverse the next link to the previous node at each step of the traversal till you reach the end of the list.

Hint # 2:

1. Create a node - `last` and initialize it to `None`.
2. Start traversing through the list by marking `head node` as the current node, till you reach to the end of the `list`.
3. Within the loop, create a temporary variable next to store the current's next node.
4. Point the next link of the current node to the `last` node, created in step one.
5. Set `last = current` and `current = next`.
6. At the end of the loop, set `head = last`, which results in the head pointing to the reversed list.
```   def reverse(self):
prev = None
while curr is not None:
temp = curr.next
curr.next = prev
prev = curr
curr = temp

### Delete the Node at a With the Given Data in a Linked List ***

Given a Singly Linked-List, implement a method to delete the node that contains the same data as the input data.

Hint # 1: Traverse over to the position with the same data as the input. Use a temporary variable to hold the previous node and point its next reference to the next reference of the current node.

Hint # 2:

1. Traverse to the required `Node` in the `list`, keeping track of the previous and current nodes.
2. Set the previous node's next pointer to `current.next`.
3. Set `current.next` to None.

Example:

``````delete(1->2->3->4,3) ==> 1->2->4
``````
```   def delete(self,data):
return None
while n.next.data != data:
n = n.next
n.next = n.next.next

### Find the “Nth from the end” Node in a List ***

Given a Singly Linked-List, write a function that returns the "Nth from the end" node of the list.

Example:

``````1->2->3->4->5->6, n=2 ==> 5
``````

Your solution should return the entire `node`, not just it's data.

Hint # 1: The problem can be solved by traversing the `Linked List` twice, one for finding the length and the other to return the position of the node.

Hint # 2: We can get the position of the `Nth Node` from the end with the formula: 'length-n+1'.1. First find the length of the List. Traverse over the `Linked List` one more time to the `Nth position` and return the `Node`. 2. Since we didn't use extra memory, the runtime is `O(n)` and space complexity is `O(1)`.

```   def find_nth_node_from_end(self, n):
count = 0
while curr != None:
count += 1
curr = curr.next

if count < n or n < 0:
return None
while count > n:
curr = curr.next
count -= 1
return curr```

### Merge Two Sorted Linked Lists ***

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

``````Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
``````
```    def mergeTwoLists(self, list1, list2):
if list1 is None:
return list2
If list2 is None:
return list1

if list1.data < list2.data:
list3 = list1
node3 = list3
list1 = list1.next
else:
list3 = list2
node3 = list3
list2 = list2.next

while list1 is not None and list2 is not None:
if list1.data < list2.data:
node3.next = list1
node3 = node3.next
list1 = list1.next
else:
node3.next = list2
node3 = node3.next
list2 = list2.next

if list1:
node3.next = list1

if list2:
node3.next = list2

return list3```

Gist content by Mary Troiani for presentation she gave at the Algorithms and Technical Interview Study Group - Dec 13, 2017 meetup

This is a part of a series of presentations for Learn Teach Code - Algorithm Study Group