Lego & Linked List

Linked List

A Linked list is a linear dynamic data structure where each node is a separate object

• Each node is comprised of two items - data and a reference to the next node
• The last node has a reference to None (null).
• The entry point into a Linked list is called Head - reference to the first node
• If the list is empty then the head is a null reference
• New node(s) can be created and then added to the head, tail or anywhere in the Linked list
• Node(s) can be removed from the head, tail or anywhere in the Linked list
• Node(s) can be rearranged on the Linked list

Linked List Advantages

• Nodes can be added and removed - memory allocation and deallocation while program is running!
• Insert and delete node(s) can be easily performed
• Ideal data structure if size is not known ahead , nodes can grow and shink
• Stack and queue can be implemented using Linked list

Linked List Disadvantages

• Linked List use more memory than list since next pointer uses storage
• Sequential access from the start - the average and worst case time complexity to find a node is O(n)
• Additional code complexity

Lego

image source: wikimedia.org

The name ‘LEGO’ is an abbreviation of the two Danish words “leg godt”, meaning “play well”. The LEGO brick in its present form was launched in 1958. The interlocking principle with its tubes makes it unique and offers unlimited building possibilities.

Interesting isn’t it? Ability to add and modify existing shapes (data structures) to build interesting shapes (data structures) to solve interesting problems is a common feature of Lego and Linked list.

Linked List problems

• Find the middle element in a linked list
• Find the nth node from the end of a linked list
• Delete a node in the linked list
• Zip a linked list
• Reverse a linked list
• Skip list

Related Articles

• Linked List Problems
• Linked List Lecture Notes@CMU

Tags

• linked list
• data structure
• algorithms