What Is A Data Structure?
A data structure is a way to store, organized/manage, and retrieve data effectively. Data structures are used in almost every program and are very important to learn and understand in software engineering.
What Is A LinkedList?
A LinkedList is a linear (O(n)) data structure that represents a sequence of elements that are the same type, which is often called Nodes. In each Node, there is the data and a pointer(s) that points to the adjacent and/or previous Node. The first node of the list is referred to as the head, and the last Node’s pointer in the list points to null or the head (Circular LinkedList). This data structure is dynamic, which means it can grow and shrink based on the number of elements inserted and deleted from the LinkedList.
To traverse a LinkedList, you have to start at the beginning (head) and go through each one until you’ve reached the desired Node. LinkedList does not allow random access.
In Java, the LinkedList implements the following interfaces, Serializable, Cloneable, Iterable, Collection, Deque, List, Queue. This is important because it gives the LinkedList data structure flexibility in its operations and usage within a program.
Below I’ll demonstrate how to build a LinkedList (Singly) and some of the operations. However, the implementation will not be as specific as the implementation in the documentation, click here for the documentation.
The Singly LinkedList has only one pointer for each Node that points to the memory address of the next Node. (See below)
The Doubly LinkedList has two pointers for each Node. One pointer pointing to the memory address of the previous Node, and the other pointer pointing to the memory address of the next/adjacent Node.