A list implements an ordered collection of values, which may include repetitions. Sepcifically, a singly linked list is a data structure that
contains a sequence of nodes such that each node contains an object and a reference to the next node in the list.
The first node is referred to as the head and the last node is referred to as the tail; the tail's next field is null.
There are many variants of linked lists, e.g, tn a doubly linked list, each node has a link to its predecessor;
A list is similar to an array in that it contains objects in a linear order.
The key differences are that inserting and deleting elements in a list has time complexity O(1).
On the other hand, obtaining the kth element in a list is expensive, having O(n) time complexity.
Lists are usually building blocks of more complex data structures.
Below are examples of a singly linkedlist and a doubly linkedlist.
For all problems in this section, unless otherwise stated, each node has two entries
- a data field, and a next field, which points to the next node in the list, with the next field of the last node being null.
Its prototype is as follows:
class ListNode:
def __init__(self , data=0, next-node=None)
self.data = data self.next = next-node
There are two types of list-related problems
- those where you have to implement your own list,
- and those where you have to exploit the standard list library.
We will review both these aspects here, starting with implementation.
Implementing a basic list APl-search, insert, delete-for singly linked lists is an excellent way to become comfortable with lists.
def search_list (L, key):
while L and L.data != key
L = L. next
# If key was not present in the List, L will have become null
return L
# Insert new_node after node.
def insert_after(node, new_node):
new_node.next = node.next
node.next = new_node
def delete_node(node):
node = node.next
#Delete the node past this one. Assume node is not a tail
def delete_after(node):
node.next = node.next.next
-
List problems often have a brute force that uses O(n) space, but a subtler solution that uses the existing list nodes to reduce space complexity to O(1)
-
Very often, a problem on lists is conceptually simple, and is more about cleanly coding what's specified, rather than designing an algorithm.
-
Consider using a dummy head (sometimes referred to as a sentinel) to avoid having to check for empty lists. This simplifies code, and makes bugs less likely.
-
It's easy to forget to update next (and previous for double linked list) for the head and tail.
-
Algorithms operating on singly linked lists often benefit from using two iterators, one ahead of the otheq, or one advancing quicker than the other.
In this section we will solve common linkedlist questions that will help us understand the data structure very well. This will in turn give us the ability to solve other linkedlist questions
-->