Implementing a lined list in Python

Jeremy Zhang

May 22, 2020·2 min read

Linked list is a list, but with each element pointing to the next element. So in a linked list, each node contains the current value of the node and a pointer to the next node.

Node

Like the graph shown above, the first node contains a value 2 and a pointer to the next node with value 4, and so on. So the implementation of a node would be:

Linked List

With the component of node implemented, let’s implement a linked list.

Add

So the first and most important function that a linked list need to fulfil is to append a new node to the end of the list.

To append a new node, we need to start from the first node in a linked list, moving to the end of it, and append the new element to the last node.

Reverse

Probably the most popular skill you need to acquire in an coding interview of linked list. To reverse a lined list, starting from the first element, we need to reverse the pointer one by one.

For each node, we reverse the pointer to assign it to previous node.

Insert

To insert a value after a certain node, we need to break the current pointer of node1 -> node2 and add 2 more pointer node1 -> new_node and new_node -> node2 .

Prepend

To add an element in front of a linked list, we need to assign the new element as head and point it to current head.

Print

Lastly, we implement a utility function to print a linked list.

Test

Example:

ln = ListNode()
ln.add(3)
ln.add(2)
ln.add(4)ln.print_list()ln.prepend(1)
ln.print_list()ln.reverse()
ln.print_list()

would produce:

[3, 2, 4]
[1, 3, 2, 4]
[4, 2, 3, 1]

[Source Code]