Introduction to Linked Lists in Python

Linked Lists are linear, dynamic, and derived data structures that can be implemented in different ways using different programming languages. Linked lists are similar to arrays in terms of usage.

The difference lies in the fact that arrays have fixed lengths while Linked Lists do not. Besides array or list elements stored in contiguous memory locations while Linked List elements are connected via link fields which hold the links to the next elements.

Linked Lists are dynamic in the sense, elements can be added in the middle of a Linked List as well as at both its ends. And Linked Lists are applied in a wide range of contexts like to implement stacks and queues, as well as to implement adjacency lists in case of graph definitions.

Traversing a Linked List refers to the act of visiting every element stored in a data structure.

Every node in a Linked List has two sections to them. One, the value field which holds the data to be stored. And two, the link field which holds the address of the next node in the sequence of nodes in the Linked List.
14421

Types of Linked Lists

There are mainly two types of Linked Lists;

  • Singly Linked Lists - These can be traversed only in one direction, and have only one link field in their node definitions
  • Doubly Linked Lists - These can be traversed in both directions, and have two link fields in their node definitions; one for the previous elements, while the other for the next one
  • Circular Singly Linked Lists - These are similar to Singly Linked Lists. The only difference lies in the fact that the last element of this type points at the Header element giving it a circular sense
  • Circular Doubly Linked Lists - These are similar to Doubly Linked Lists. The only difference lies in the fact that the last element of this type points at the Header element, while the Header element points back at the last one, thus giving it a circular sense

Constituents of a Linked List in Python

Linked Lists in Python can be implemented using the object-oriented characteristic of Python.

The two main classes to be built to implement Linked Lists are :

  1. Node class - These represent the actual data elements that a Linked List is made of. The fields included in the Node class are
    1. value - This field holds the actual data that element of the Linked List represents
    2. next/ right - This field holds the link to the next element in the Linked List, which is used to move to the next element while traversing the Linked List
    3. left (optional) - This field holds the left hand or previous element of Circular Linked Lists, which is used to move to the left hand or previous element while traversing the Linked Lists
  2. LinkedList class - This class actually holds the form of the Linked List, as well as all the associated fields and methods to manipulate the same
    1. Fields in class
      1. head - The header field holds the header or first element of the Linked List. When the Linked List is empty, it holds 'null' value
    2. Methods in class
      1. add() - This method is used to add elements to a Linked List. It has three options; to add at the beginning, to add at the end, and to add in between
      2. delete() - This method is used to delete elements from a Linked List. It has three options; to delete at the beginning, to delete at the end, and to delete in-between. Deletion can also be based on the value
      3. display() - This method is used to represent the Linked List in a user-comprehendible manner
      4. length() - Returns the length of the Linked List

Advantages and Disadvantages of Linked Lists

Advantages
  • Dynamic memory allocation - Memory is allocated and deallocated efficiently so that minimum and efficient memory usage is practiced
  • Easy implementation - Linked Lists are often easy to use in certain situations
  • Insertion and deletion is carried out using pointers which again very easy to use
Disadvantages
  • Memory overhead - There is a certain memory overhead that is used by the pointer used to access as well as the classes used
  • Time-consuming - Traversal or access is time-consuming as direct access is not possible. All the elements need to be traversed to reach a certain value
  • Random access - Random access is not possible due to dynamic memory allocation

Applications of Linked Lists

  • Implementation of stacks and queues
  • Dynamic memory allocation
  • Implementation of the adjacency list in graph theory applications
  • Prevention of collision in hash maps
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions