wk5&&6 (LinkedLists)

 0    10 flashcards    up804653
download mp3 print play test yourself
 
Question English Answer English
Define a linear data structure
start learning
Linear data structure: a collection of nodes (elements) where each node has a unique predecessor and a unique successor.
what are the disadvantages of an array compared to a linked list
start learning
An array is a static structure Disadvantages of using arrays: Cannot be easily extended or reduced to fit the data set. Can be expensive to maintain
Define a linked list
start learning
Linked list is a collection of objects, called nodes Every node has two components information to be stored (the data) reference to the next node (often called a link).
What is meant by a dynamic data structure?
start learning
The number of nodes in the list is not fixed. The linked list can grow and shrink on demand.
What are the advantages of a linked list
start learning
Easily extended or reduced to fit the data set. Efficient O(1) to insert/delete item, once located.
What are the disadvantages of linked lists
start learning
Does not allow direct access to individual items. To access a particular item: Start at the head and then Follow references until you get to the item O(n) Uses more memory compared to an array: Need to store a reference to the next node.
What is a singly linked list?
start learning
A linked list that goes in one direction from start to end
what is a circularly linked list?
start learning
the last node of a SSl links to the firts node
What is a doubly linked list?
start learning
each node has the address of the previous and the next node
what is a skip list?
start learning
data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one.

You must sign in to write a comment