Discover the advantages and disadvantages of using a linked list so that you know when it is the best data structure to use for your use case. Learn the runtime complexity each linked list operation takes in terms of Big O notation.
- There are many different data structures…we can use for our data, and a linked list is one of them.…We can compare its operations independently of input,…with Big O Notation, which describes the performance…or complexity of an algorithm.…Some of the operations we've looked at are…Access, Update, Insert, Search and Delete.…Again, for each of these, we can come up with its…run time complexity to determine how much…computational time each operation takes…as compared to the others with the linked list.…
For accessing an item with a linked list,…the best case is if the item we are trying to access…is the first item in the linked list.…If this is the case, then it takes constant time…because we just grab the head of the list…with the name of the list dot head.…If we want to get the last item of a singly linked list,…then we need to follow all of the next nodes,…until we find that item.…This means accessing could take…linear time in the worst case…because we need to grab each item to find the next one.…
Updating also takes O of N time…
- Data types: Booleans, numbers, strings, and more
- Multidimensional arrays
- Jagged arrays
- Search and sort arrays
- Linked lists
- Stacks and queues
- Hash functions and hash tables
- Trees and graphs
Skill Level Intermediate
Understand data structures1m 25s
1. Introduction to Data Structures
4. Stacks and Queues
5. Hash-Based Data Structures
6. Trees and Graphs
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.