LinkedList Flashcards
Is a Linked List Random or Sequential Access?
Sequential
Is a LinkedList a linear data structure?
Yes
Each element is created as a separate…
Object
What is each individual element called?
Node
A Node is made up of two parts. What are they?
- The data (could be complex objects)
2. The reference (or pointer) the the next Node in the List.
What is a real-world analogy for a ACCESSING an element in a LinkedList?
A tape measure. To get to inch 72 you first have to traverse inches 1 through 71.
How do we know when we have reached the end of a LinkedList?
The reference to the next Node will be null.
What is the term for the first Node in a LinkedList?
The HEAD Node.
What is the term for the last Node in a LinkedList?
The TAIL Node.
Data can flow in and out of …. point of a LinkedList.
Any
What are the three places in a LinkedList that we can ADD or REMOVE data?
HEAD, MIDDLE, TAIL.
How do we ADD a Node to the Head of LinkedList?
We make the new head Node point to the old head Node and update what Node we consider to be the head node in our implementation.
How do we DELETE a Node from the Head of LinkedList?
We make the 2nd Node in the list our new head Node and make the old head Node point to null.
How do we ADD a Node somewhere in the middle of a LinkedList? (2 steps)
- Make the pointer of the new Node point to the Node after the location we want to insert at.
- Set the Node before the location we want to insert at to point towards the new Node.
How do we REMOVE a Node somewhere in the middle of a LinkedList? (1 step)
Make the pointer of the Node previous to the one we’re removing, to now point to the Node after the one we’re removing.
How do we REMOVE a Node at the tail of a LinkedList?
Set the previous tail to point to a null value instead of the current tail.
What is the BigO of ACCESSING an element in a LinkedList?
O(n). Sequential data structure, worst-case you have to go via every element in the list.
What is a pirate themed analogy of a LinkedList?
It’s like a treasure map. You follow the directions to one place and then it tells you the where to go to find the next place and so forth.
What is the BigO of SEARCHING for an element in a LinkedList?
O(n). Must do Linear Search.
What is the BigO of INSERTING an element in a LinkedList? (2 depending on location)
- If inserting at the head of the list then O(1)
2. Anywhere else then it’s O(n)
What is the BigO of DELETING an element in a LinkedList? (2 depending on location)
- If deleting at head of the list then O(1)
2. Anywhere else then it’s O(n)
Examples of uses for LinkedLists?
Music playlists. The track info is the data and it points to the next song in the playlist.
PhotoViewing app, the ‘next’ button links to the next image in the list.
As the ‘backing’ data structure for other data structures like Queues and Stacks
What is a Singly-LinkedList? What is its main drawback? And what data structure gets around this drawback?
The pointers/references only point to the next Node in the list. You can’t navigate back towards the head node. With a Doubly-LinkedList you can traverse the list in either direction.
