Linked Lists - Info Flashcards
Linked Lists
A linked list is, along with a________, a way of storing a list in memory.
Linked lists and arrays are data structures that store objects in a linear order.
The order in a linked list is determined by a p__________.
arrays
pointer
Singly Linked Lists
The elements of a singly linked list are not c___________ like array elements.
They are linked together, and therefore as well as holding some data, they also have a ‘next’ section which holds the address of the next element in the list.
This is the link.
contiguous
Singly Linked Lists - Direction
You can only move in a f__________ direction in a singly linked list.
forward
Singly Linked Lists - Composition
The elements in a linked list are called n____________.
Each node contains two parts:
D________
L_________
Nodes
Data
Link (next)
Singly-linked list - Pointer
In order to access the first node in a singly linked list, we need a pointer that contains the address of that first node.
We call this pointer the ‘h_______’,
head
Singly Linked list
The last item in a singly linked list will have N______ as its address.
NULL
Inserting and Deleting Elements to Single linked lists
It is easy to insert and delete nodes in a singly linked list, as all we have to do is change the p__________ (addresses).
In arrays, we have to shuffle elements along the list which can take a lot of time if you have a large array.
Both take O(1)
pointers
Singly Linked Lists - Searching
It is difficult to search a singly linked list as the elements do not have indices like array elements.
To locate an element we need to begin at the h_______ and work our way towards the t___________ until we find the one that we want.
This takes O(n) time.
head
tail
Doubly Linked Lists - Nodes
The nodes of a doubly linked list have three sections;
D________
N________
P_________
DATA
NEXT
PREV
The previous section has the address of the p________ node, so we can move in both directions in doubly linked lists.
previous
Doubly Linked Lists - Search, Insert and Delete
It takes O( ) time to search a doubly linked list.
Insert = O(1)
Delete = O(1)
O(n)
Sentinels
See YouTube Video
