each element sits in own block of memory (called node)
nodes can only be accessed in sequential order
appears limited
size varies - nodes allocated on need basis
list elements can be easily inserted/removed without reallocation and at any point in the list
no random access to data
no efficient form of indexing
Key Differences
underlying layout of data in memory
how individual elements are accessed
Linked Lists Properties
overview
a sequence of elements arranged 1 after another with each element connected to next by a link
one of the simplest and most common data structures
can be used to implement other abstract data types
defintion
data structure of group of nodes that represent a sequence
diagram
above is a linked list with nodes that contain 2 fields - an integer value and a link to next to the next node; last node linked to terminator symbol to signify end of list/null link
conceptual implementation
each node has data and reference (link) to next node in sequence
allows for insertion of removal of elements from any position in sequence
operations for singly linked list
insertion
deletion
traversal - going through entire sequence until reaching last node
advantages
dynamic data structure that allocates needed memory
easy implementation for insertion and deletion operations
other data structures can be easily executed with linked lists
reduce access time and can expand without more memory being used
disadvantages
usually wastes memory with pointers which requires extra storage space
nodes must be read sequentially
nodes stored in an in-contiguous manner, so more difficult to access individual nodes
very difficult to reverse traverse
Linked Lists Algorithms
constructor for an integer node in a linked list\
public Int_Node (int initialData, Int_node
initialLink) {\
data = initialData; //integer value\
link = initialLink; //reference to next node in list\
}\
define empty linked list\
pseudocode representing empty list by storing null in head reference\keeping track of front node by using an Int_Node reference variable called head
add new node to empty list\
pseudocode
create new node for head
place data in new node’s data field
make head refer to null which is initial head value
connect new node to head
add node to front of list\
pseudocode
create new node
place data (newData) in new node’s data field
connect new node to front of list
make original head refer to new head of linked list
Diagram showing how a node is inserted after an existing nodeInserting node before existing node cannot be done directly - instead you have to keep track of the previous node and insert a node after that
adding anywhere but front\
previous.link);
while (prev.link != null) {\
prev = head;\
prev = prev.link;\
}\
pseudocode set a reference named prev (for previous) to refer to node which is just before new node’s position
removing node at head\
pseudocode directing head to node right next to it (head.link) so that original head is removed
removing node anywhere
Removing node after given node - to find and remove a particular node, you still have to keep track of the previous element
traverse through list\
while (pointer != null) {\
pointer = pointer.link;\
}\
pseudocode
initializing pointer to reference head
while loop that keeps going through entire list until pointer (or head) is null\null implying that it’s reached the last node because the last node will always have a null link since there’s nothing next to the last node so no link so null link
pointer referenced to next node or pointer.link
print list through traversal\
while (pointer != null) {\
System.out.print(pointer.data + " ");\
pointer = pointer.link;\
}\
pseudocode\same as traversal algorithm but just printing out data of pointer as you go along the node sequence with pointer.data