In this section, we introduce a data structure known as a linked list, which provides an alternative to an array-based structure. A linked list, in its simplest form, is a collection of nodes that collectively form a linear sequence. In a singly linked list, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list. | Singly Linked Lists 3/18/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Singly Linked Lists © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 1 Singly Linked List ! A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer ! Each node stores n head n next element node element link to the next node ∅ A B © 2014 Goodrich, Tamassia, Goldwasser C Singly Linked Lists D 2 1 Singly Linked Lists 3/18/14 A Nested Node Class © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 3 Accessor Methods © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 4 2 Singly Linked Lists 3/18/14 Inserting at the Head • Allocate new node • Insert new element • Have new node point to old head • Update head to point to new node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 5 Inserting at the Tail • Allocate a new node • Insert new element • Have new node point to null • Have old last node point to new node • Update tail to point to new node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 6 3 Singly Linked Lists 3/18/14 Java Methods © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 7 Removing at the Head • Update head to point to next node in the list • Allow garbage collector to reclaim the former first node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 8 4 Singly Linked Lists 3/18/14 Java Method © 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists 9 Removing at the Tail • Removing at the tail of a singly linked list is not efficient! • There is no constant-time way to update the tail to point to the previous node © 2014 Goodrich, Tamassia, Goldwasser Singly Linked .
