wk5&&6 (LinkedLists)

Define a linear data structure

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

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

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?

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

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

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?

A linked list that goes in one direction from start to end

what is a circularly linked list?

the last node of a SSl links to the firts node

What is a doubly linked list?

each node has the address of the previous and the next node

what is a skip list?

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.