Skip to content

Latest commit

 

History

History
 
 

linkedlist

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
check_if_circular_linked_list.py
check_if_circular_linked_list.py
 
 
circular_linked_list_insertion_at_pos.py
circular_linked_list_insertion_at_pos.py
 
 
circular_linked_list_traversal.py
circular_linked_list_traversal.py
 
 
doubly_linked_list_insertion.py
doubly_linked_list_insertion.py
 
 
inked_list_reverse_iterative.py
inked_list_reverse_iterative.py
 
 
length_of_linkedlist.py
length_of_linkedlist.py
 
 
linked_list_deletion.py
linked_list_deletion.py
 
 
linked_list_insertion.py
linked_list_insertion.py
 
 
linked_list_operations.py
linked_list_operations.py
 
 
linked_list_reverse_recursive.py
linked_list_reverse_recursive.py
 
 
linked_list_search_element.py
linked_list_search_element.py
 
 
merge_sorted_list_iterative.py
merge_sorted_list_iterative.py
 
 
merge_sorted_list_recursive.py
merge_sorted_list_recursive.py
 
 
middle_ele_of_linked_list.py
middle_ele_of_linked_list.py
 
 

README.md

Linked List

Information

A linked list is a data structure where each element is called a node and where each node holds two types of information:

  1. a field that could contain some data related to the node
  2. a pointer or reference to the next element in the list

Can we reverse a linked list in less than O(n) ?

It is not possible to revert a linked list in less than O(n) as the complexity grows linearly with the number of nodes in the linked list. One needs to pass through each node to update the reference. Do note that this could be done in one forward pass.

Double linked list can be reversed with a time complexity of O(1) as only the head and the tail of the linked list require an inversion.