Linked List Data Structure

• Linked list

– Linear collection of self-referential class objects, called nodes

– Connected by pointer links

– Accessed via a pointer to the first node of the list

– Subsequent nodes are accessed via the link-pointer member of the current node

– Link pointer in the last node is set to null to mark the list’s end

• Use a linked list instead of an array when

– You have an unpredictable number of data elements

– Your list needs to be sorted quickly

• Types of linked lists:

– Singly linked list

• Begins with a pointer to the first node

• Terminates with a null pointer

• Only traversed in one direction

– Circular, singly linked

• Pointer in the last node points back to the first node

– Doubly linked list

• Two “start pointers” – first element and last element

• Each node has a forward pointer and a backward pointer

• Allows traversals both forwards and backwards

– Circular, doubly linked list

• Forward pointer of the last node points to the first node and backward pointer of the first node points to the last node