# Lego & Linked List

Aug 15, 2016

## 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

## Tags

- linked list
- data structure
- algorithms