Data Structures are a way to organize and store data and are very fundamental topics for software developers to understand.
“I will, in fact, claim that the difference between a bad programmer and a good one is whether she considers her code or her data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus
We use different data structures based on necessity, therefore choosing the most efficient data structure is informed by your needs. There are different data structures each necessary for efficient design of algorithms and data processing.
Linked Lists according to Google is:
An ordered set of data elements, each containing a link to its successor (and sometimes its predecessor).
The latter are defined as doubly linked lists. Linked Lists are often compared to arrays since they both store a sequence of elements although using different techniques. They can be visualized as nodes where every node holds a data element and points to the next node.
Primary operations on this data structure are: inserting, deleting and searching.
Defining a Linked List
When inserting a new node element, you first create it then determine where it needs to be added.
You find the node to be deleted and change the target node of the previous element of that to be deleted to that of the next one after the element to be deleted.
You can search for an element in a linked list using the index.
You can also search for the index of a particular node element.
Linked Lists vs Arrays
From the above implementation, Linked Lists are definitely similar to arrays in terms of they both store a sequence of elements and are accessible through position indices. So what makes the two different?
- You can quickly access a value at random in an array. Arrays have a O(1) random access while Linked Lists have a O(n) since they only allow sequential access to the elements.
- Insertion and Deletion are cheaper with Linked Lists. If an array is of size 1000 and we want to add an element at position 100 every element after that will have to be moved and that’s expensive for memory. Inserting a new element in a Linked List pretty much just means changing the pointer to the new node element.
- Linked List can act as purely functional data structures(interesting point)