Workshop 6 - Linked Lists

Question 1

Linked List

Answer 1

Collection of objects, called nodes.

Every node has two components, INFORMATION to be stored and REFRENCE to the next node.

Question 2

Dyanmic Data Structure

Answer 2

Linked List is an example of this.

Number of nodes can grow if not fixed list.

Linked List can grow and shrink on demand.

Question 3

Linked List advantages

Answer 3

Easily extendable or reduced to fit in data set.

Efficient - O(1) to insert/delete, ONCE LOCATED.

Question 4

Linked List disadvantages

Answer 4

Does not allow direct access to individual items.

To find particular item, start at head and follow references till you get to the item. O(n)

Uses more memory. NEED to store a reference to next node.

Question 5

Representation of Single Linked List in Java

Answer 5

recursive definition

data - integer

link - refrence table

Question 6

Linked List example.

How do you know you reached end of queue?
How do you knkow if item removed?
What happens if you start at the start?

Answer 6

refrence link value = returns null value

you dont get acess to the other nodes.

you cannot. linking in one direction. no information about predessor.

Question 7

Dummy Node

Answer 7

gives null value

Question 8

Doubly Linked Liust

Answer 8

One more refrence, more flexibility.

more space disadvanatge,

Question 9

SkipList

Answer 9

Probablistic data structure.
Based on set of parallel linked lists.
Improved efficiency.

SkipList data stored in order.
During search it parts of list can be skipped.

Efficiency O(log2n)