COMP 2402 Chapter Notes - Chapter 3: Double-Ended Queue, Ob River, Doubly Linked List
Document Summary
Linked lists are pointer based data structures. Linked lists are made up of nodes that contain the list items. References (pointers) are used to link the nodes together in a sequence. A disadvantage of linked lists is that they cannot get an element or set an element, using get(i) and set(i, x), in constant time. Linked lists walk through the list one element at a time until the ith element is found. The primary advantage of linked lists is, given a reference to any list node u, we can delete u or insert a node adjacent to u in constant time (no matter where u is in the list) A sequence of nodes where each node u stores a data value u. x and a reference u. next to the next node in the sequence. For the last node w, w. next = null class node {