SCC.121: Fundamentals of Computer Science - Linked Lists Notes

Definition: A list is an Abstract Data Type (ADT) that organizes a collection of items in a linear order.
Characteristics:
- No duplicate items are allowed within the list.
- The assumption is made that the user will not provide duplicates, relieving the implementation of the need for duplicate checking.
Applications:
- Widely useful in various domains including:
- Shopping lists
- Friends lists on social media platforms
- Student records management systems
- To-do lists

Definition: A special type of linked list where each element contains pointers to both the next and the previous elements.
Element Structure:
- An element in a doubly linked list is structured as follows:
- Element { Item data; Element next; Element prev; }
- Here, data represents the item, next is a pointer to the next element in the list, and prev is a pointer to the previous element.
Operations:
- add(L, Element e): This operation adds element e to the list L.
- remove(L, e): This operation removes element e from the list L.
- search(L, Item k): Uses the list L to search for item k. It returns a pointer to the element containing k if k is present; otherwise, it returns nil.
- size(L): Returns the total count of items in the list L.

Constructor:
- The initial constructor for a doubly linked list is as follows:
- List() { Element head = nil; }
- Here, head indicates the starting point of the list and is initially set to nil, indicating that the list is empty.

Doubly Linked List Visualization:
- An element can be represented graphically as:
- / represents a pointer with a value of nil.
- Examples of operations can be represented as follows:
- add(L, e) results in modifying pointers for inserted elements.
- For instance:
  - Adding an element 5 followed by 6 might look like `L.head -> /data5/next -> /data6/next
The internal structure when modifying the head of the list shows how pointers are updated:
- Before insertion: L.head -> /
- After insertion: L.head -> /data5/data6/
- New head updates pointers to include the recently added elements.

Search Operation:
- The implementation for searching an item k in the list L is as follows:
```
search(L, k) {
    p = L.head;
    while (p != nil && p.data != k) {
        p = p.next;
    }
    return p;
}   
```
- This code iteratively traverses the list until it finds the desired item or reaches the end.
Addition Operation:
- The addition of an element e at the head of the list is executed using:
```
add(L, e) {
    e.next = L.head; // Adding at the front
    if(L.head != nil) {
        L.head.prev = e;
    }
    L.head = e;
    e.prev = nil;
}   
```
- This changes the head of the list to the newly added element, effectively placing e at the front.
Removal Operation:
- The removal of an element e from the list utilizes:
  remove(L, e) { if (e.prev != nil) { // Not the first element e.prev.next = e.next; } else { L.head = e.next; } if (e.next != nil) { // Not the last element e.next.prev = e.prev; } }
- This ensures that pointers are properly re-linked, either adjusting the head pointer if the element to be removed is the first element or linking adjacent nodes.

Characteristics:
- A singly linked list differs from a doubly linked list by not including a previous pointer.
- This restricts traversal to only the forward direction, making certain operations, such as printing the list in reverse order, more complicated.
- Removal operations always require traversal through the list since there is no backward referencing.

Variations:
- Different variants of linked lists allow for:
- Inserting and removing elements at specific positions within the list.
- Removal of elements based on data.
- Implementing iterators such as getFirst() and getNext() for efficient traversal.
- Including a tail pointer in a doubly linked list which may point to the end of the list, simplifying reverse traversal.
- Utilizing Sentinels, which are special markers, can simplify certain aspects of the implementation and improve code clarity.