LinkedList Flashcards
What is a Linked List
A group of nodes (value, address) in sequence
Each node has a reference to the next node
First node is head, last node is tail
What is a Linked List in Java?
LinkedList in Java is a class that implements the List and Deque interfaces using a linked list data structure. A linked list is a data structure that consists of a sequence of elements, where each element points to the next element in the sequence.
In a LinkedList, each element is represented by a node that contains the element itself and a reference to the next node in the list. The first node in the list is called the head, and the last node is called the tail.
Some of the key features of LinkedList include:
- It allows null elements.
- It provides methods to add and remove elements at any position in the list, such as add, remove, and set.
- It provides constant-time performance for adding or removing elements at the beginning or end of the list, such as addFirst, addLast, removeFirst, and removeLast.
- It allows iterating over the elements in the list using an iterator or a for-each loop.
LinkedList is a useful data structure when we need to insert or remove elements frequently at any position in the list. However, accessing elements by index is slower than with an array-based list, since we have to traverse the list from the head or tail to the desired index. Therefore, LinkedList is generally not recommended for programs that require frequent random access to elements by index.
Overall, LinkedList provides a flexible and efficient implementation of a linked list data structure in Java, which is useful in many applications, such as graph algorithms and certain kinds of data processing.
What is the time complexity of removing from the start and adding to the end of a Linked List?
O(1)
What is the time complexity of a look up of a Linked List?
O(n)
What is the time complexity of inserting an element in the middle of LinkedList?
O(n) because you have to search through each element sequentially
What is the time complexity of deleting a node from the end of a Linked List?
O(n) because you have to search through each element sequentially
Is a LinkedList synchronized?
No, but we can get a synchronzied version of it:
List l = Collections.synchronizedList(new LinkedList(…));
What is the difference between Arrays and LinkedLists?
The main difference between an array and a linked list is their underlying data structure and how they allocate memory for storing elements.
Arrays:
- Allocate memory for all elements as a contiguous block in advance
- Have a fixed size that cannot be changed during runtime
- Provide direct access to elements using an index
- Can be faster for accessing elements by index
- Insertion and deletion can be expensive, especially in the middle of the array
Linked Lists:
- Allocate memory only when a new element is added
- Can grow or shrink dynamically
- Require traversing the list to access elements
- Can be faster for inserting or deleting elements in the middle of the list
- Provide a flexible data structure for dynamic data sizes
What are the key differences between a singly linked list and a doubly linked list?
Singly Linked List:
- Each node contains a reference to the next node in the list
- Cannot be traversed in reverse order efficiently
- Requires less memory per node than a doubly linked list( 1 reference only)
- Less complex and easier to implement than a doubly linked list
- Suitable for applications where elements are only accessed sequentially or from the front of the list
Doubly Linked List:
- Each node in a doubly linked list contains references to both the next and the previous nodes in the list
- Can be traversed in both forward and reverse order efficiently
- Requires more memory per node than a singly linked list, as it needs to store two references
- More complex and harder to implement than a singly linked list
- Suitable for applications where elements are accessed both from the front and the back of the list
