Linked Lists and Arrays - kimschles/schlesinger-knowledge GitHub Wiki
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