In this ?Data structures in Python? series, I?ll go over the 6 major data structures that will come up in any kind of software engineer job/internship interviews. They are linked lists, stacks/queues, hashes, heaps and trees.
I chose Python as the primary language for this series because of its readability and the ease in implementing data structures. In fact, both Harvard and MIT have their intro CS courses offered in Python.
I?ll cover linked lists today. You can find the source code for the coding challenges below here. Let?s get started.
What is a linked list?
Here?s an image of a linked list. Two key things to note:
1: A linked list consists of nodes.
a node
2: Each node consists of a value and a pointer to another node.
a value
a pointer
The starting node of a linked list is referred to as the header.
Essentially, linked list is a chain of values connected with pointers.
Why use linked lists?
Linked list is often compared to arrays. Whereas an array is a fixed size of sequence, a linked list can have its elements to be dynamically allocated. What are the pros and cons of these characteristics? Here are some major ones:
Advantages
A linked list saves memory. It only allocates the memory required for values to be stored. In arrays, you have to set an array size before filling it with values, which can potentially waste memory.
Linked list nodes can live anywhere in the memory. Whereas an array requires a sequence of memory to be initiated, as long as the references are updated, each linked list node can be flexibly moved to a different address.
Disadvantages
Linear look up time. When looking for a value in a linked list, you have to start from the beginning of chain, and check one element at a time for a value you?re looking for. If the linked list is n elements long, this can take up to n time. On the contrary many languages allow constant lookups in arrays.
Linked lists in Python
Here?s how you implement a linked list in Python:
This is a node class.
class Node: def __init__(self,val): self.val = val self.next = None # the pointer initially points to nothing
Once you have the Node class, you can implement any linked list as follows:
Example linked listnode1 = Node(12) node2 = Node(99) node3 = Node(37) node1.next = node2 # 12->99node2.next = node3 # 99->37# the entire linked list now looks like: 12->99->37
You might have wondered why I didn?t implement a LinkedList class. After all, linked list is just a bunch of nodes connected together. We can refer to a header node as the linked list that?s started from there. In the above example, node1 is the header node, and it can also represent the linked list that starts from it. If you?re curious about the implementation involving a LinkedList class, take a look here.
Traversing values
class Node: … def traverse(self): node = self # start from the head node while node != None: print node.val # access the node value node = node.next # move on to the next node
Values can be traversed like this. You start from the head node, check its value, and move on to the next node. Once you hit the end of the linked list, the node should not have any value (None).
Side Note: It?s weird to talk about linked lists in python because this data structure is too low level to be useful in python programs. So don?t blame me if you don?t see the point of coding all this in Python. After all, there?s not much point in using linked list in Python besides its educational value and usefulness in coding interviews. In other languages like C and C++, where linked lists are actually crucial to any programs you?re implementing.
[Advanced] Doubly linked lists
As the name suggests, each node in a doubly linked list has two nodes: one pointing to the next node and one pointing to the previous node. Here?s the Python implementation:
class DoublyNode: def __init__(self, val): self.val = data self.next = None self.prev = None
Advantages over singly linked list1) Can be traversed in both forward and backward direction.2) The delete operation is more efficient (take a look at p4 below and contrast it with the delete operation for a doubly linked list).
Disadvantages over singly linked list1) Every node requires extra space for a previous pointer.2) All operations require an extra pointer to be maintained.
Some linked list coding challenges
Here are the challenges for you to get more familiar with linked lists. Most challenges are taken from ?Cracking the Coding Interview? book.
- Traverse a linked list
- Remove duplicates from a linked list
- Get the kth to last element from a linked list
- Delete a node from a linked list
- Add two linked lists from left to right e.g. 1->2->3 + 8->7 => 321+78 = 399
- Add two linked lists from right to left e.g. 1->2->3 + 8->7 => 123+87 = 210
My solutions can be found here. Feel free to send me a pull request or leave a comment here if you have any questions or found mistakes in my solutions.
In the next post, I?ll cover stacks and queues.
