Skip to content

Instantly share code, notes, and snippets.

@ThuyNT13
Last active Jan 15, 2018
Embed
What would you like to do?
LinkedList overview

What are linked lists?

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.

Linked List

Image from: https://www.tutorialspoint.com/data_structures_algorithms/linked_lists_algorithm.htm

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[0] is “Chicago” and array[4] 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:

Image from: https://www.tutorialspoint.com/data_structures_algorithms/linked_lists_algorithm.htm

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[1]. 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:

Image from: https://www.tutorialspoint.com/data_structures_algorithms/linked_lists_algorithm.htm

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
class LinkedList:
	def __init__(self):
		self.head = None

	def setHead(self, head):
		self.head = head

We can create the head of our list like this:

my_list = LinkedList()
node = ListNode(10)
my_list.setHead(node)

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

def insertAtEnd(self, data):
	node = ListNode(data)
	if self.head is None:
		self.setHead(node)
	else:
		curr = self.head
		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):
        if self.head:
            n = self.head
            c = 1
            while n.next:
                n = n.next
                c += 1
            return c % 2 == 0
        return True
OR:  def is_list_even(self):            
        current = self.head
        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
        curr = self.head
        while curr is not None:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        self.setHead(prev)

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):
        if self.head is None:
            return None
        if self.head.data == data:
            self.setHead(self.head.next)
            return self.head
        n = self.head
        while n.next.data != data:
            n = n.next
            if not n: return self.head
        n.next = n.next.next
        return self.head

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
        curr = self.head
        while curr != None:
            count += 1
            curr = curr.next

        curr = self.head
        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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment