Linked Lists and Arrays

Describe Arrays

• A linear data structure; they have a sequence and order and they have to be traversed in sequence
• Requires a certain amount of memory in one block

List Common Uses for Arrays

Describe Linked Lists

• A linear data structure; they have a sequence and order and they have to be traversed in sequence
• A series of nodes
• The first node is called the head
• The last node points to null
• Each node only knows its data and pointers; it doesn't know about any other parts of the list

Singly Linked Lists

• In a singly linked list, each node contains data and a pointer to the next node

Doubly Linked Lists

• Each node contains data, a pointer to the previous node and a pointer to the next node

Circular Linked Lists

• Instead of the final node pointing to null, there is a tail node
• The tail node points to the beginning of the list

List Common Uses for Linked Lists

Explain how to add a node to the beginning of a singly linked list

List the tradeoffs between arrays and linked lists

• An array requires a contigous block of memory, whereas linked lists can store data in different places.
• Arrays are static data structures and linked lists are dynamic
  • Static data structures need all their memory allocated upfront
  • Dynamic data structures can use memory as needed

Learning Resources