Introduction to Linked Structures Flashcards
Problems with arrays
Insertions and deletions require shifting elements, and O(n) operation
Length is fixed at instantiation, resizing requires new memory and transfer of element
Why do we have these problems with arrays?
Array cells map to adjacent cells in memory, to support constant-time access
There is a one-to-one correspondence between the logical structure of the sequence of elements and the underlying memory storage
How can we solve the problems we have with arrays?
Decoupling the logical sequence and the memory representation
What does a linked structure allow us to do?
A linked structure allows us to represent a sequence of elements independently of their positions in memory
What do and do not linked structures support?
Linked structures support insertions, deletions, and traversals
Linked structures do not support random access
How is storage allocated in linked structures?
Storage is allocated for each new element, as needed, from an area of memory called the system help
Of what does a linked structure consist?
A linked structure consists of a unique external link which is either empty or points to a node
What does a node contain?
A data element and a link to the next node
What does the last node in a linked structure contain?
An empty link
What does the variable representing a linked structure contain?
The address of the first node in the linked structure
What is None?
The memory address 0
What are links also sometimes called?
Pointers or references
What are some of the benefits of linked structures?
The logical size and the physical size of the structures are always the same
Memory is allocated for new nodes only when needed
Storage for deleted nodes is reclaimed by the system
Array tradeoffs
Contant-time access is good for binary search, implementing a dictionary, etc.
Uses less memory if the array is close to full
Linked structure tradeoffs
Uses memory only as needed, never have to resize
Insertions and removals need no extra overhead to shift data elements
But accesses, replacements, insertions, and removals at arbitrary positions are O(n) in time
