List: LinkedList - Githubissues

YuezhenQin commented 11 months ago

LinkedList

Arrays are implemented under the hood in a way that the elements are stored contiguously in memory. Let's say you declared an array to hold 32 bit integers. Each element in the array is at an address that is 4 bytes (32 bits) away from its neighbors. This allows the programmer to access elements in an array with indexing (like arr[1] etc.).

A linked list is a data structure that is similar to an array. It also stores data in an ordered manner, but it is implemented using node objects (will have a custom class that defines the node object). Each node will have a "next" pointer, which points to the node representing the next element in the sequence.

Node

A node is an abstract data type with two things. First, a node stores data. This data can be whatever you want - an integer, a boolean, a hash map, your own custom objects, or all of the above. Second, a node stores pointers to other nodes.

In LL, the nodes are out of order in actual memory in the way we're going to connect them. What this means is that LLs are not stored in memory the same way that we use them as programmers. They could be in some random order in the memory, but they're connected via pointers. We could have some big mess like this in memory, but as programmers we're gonna have something nice and clean like this. So this is a difference from a linked list compared to arrays. Arrays are stored in the same way in the memory, but linked list as we can see are not necessarily stored in the same way in memory. There is a 'next' for us to connect node 1 to node 2.

Advantages and disadvantages compared to arrays

The main advantage of a linked list is that you can add and remove elements at any position in O(1). The caveat is that you need to have a reference to a node at the position in which you want to perform the addition/removal, otherwise the operation is O(n), because you will need to iterate starting from the head until you get to the desired position. However, this is still much better than a normal (dynamic) array, which requires O(n) for adding and removing from an arbitrary position.

Linked lists also have the advantage of not having fixed sizes. While dynamic arrays can be resized, under the hood they still are allocated a fixed size - it's just that when this size is exceeded, the array is resized, which is expensive.

The main disadvantage of a linked list is that there is no random access. Linked lists also have more overhead than arrays - every element needs to have extra storage for the pointers.

Mechanics of a linked list

Assignment A large part of linked lists is moving pointers around. It's important to build an intuition behind how to correctly re-assign pointers and the order in which the re-assignments should happen.
Chaining .next
Iteration

Types of LinkedLists

Singly-Linked List: Node (E e, Node next)

Doubly-Linked List: Node (E e, Node prev, Node next)

Linked List with sentinel nodes

The idea is that, even when there are no nodes in a linked list, you still keep pointers to a head and tail. The real head of the linked list is head.next and the real tail is tail.prev. The sentinel nodes themselves are not part of our linked list.

The sentinel nodes also allow us to easily add and remove from the front or back of the linked list. Recall that addition and removal is only O(1) if we have a reference to the node at the position we are performing the operation on.

Dummy pointers

Sometimes, it's better to traverse using a curr pointer and to keep head at the head.

Using the "curr"pointer allows us to traverse the linked list without losing a reference to the head.

curr = head;
while (curr != null) {
    curr = curr.next;
}

Circular-Linked List

add()
remove()
removeAll()
toString()
while iteration
for iteration