#linkedlists

New Tutorial on Linked Lists Up Now!

Hey World! Check out my latest video on Linked Lists! In this video, I explain what Linked Lists are, I compare them to arrays, show the structure, code, basic operations, time and space complexities, and a couple of fun facts.

Go to my github account:(https://github.com/estefanniegg/estefannieExplainsItAll/blob/master/mergeSort) to check out the code if you want to follow along!

Subscribe to my channel if you’d like to be the first to know when I publish the next video :) Code on dudes and dudettes!

The week prior to reading week included our midterm, and an expansion of our lessons in linked lists. I learned of linked lists in grade 12 (last year), and up until just recently I haven’t found a reason for linked lists to be used! They’re confusing, take a while to learn, and are not built in to any given language. 

When my class went over them in Java in grade 12, I remember the concept being a little harder to grasp. This experience with the concept really helped me in visualising and using linked lists.

The way I like to explain linked lists is to treat it literally as the name suggests. It’s a linked list! Each element in a linked list is called a node, and are treated almost as a list with two variables, one being the value, and the other being a pointer, which points to another node. 

The reason for using linked lists over builtin lists is the way it is stored in memory. Linked list’s nodes can be stored at any valid point in memory, while lists are stored together in one huge part of memory.

design an iterator over a LinkedList of LinkedList’s

import java.util.Iterator; /** * @author Sabuj Das * */ public class LinkedList implements Iterable{ private Node head; public void add(T item){ if(head == null){ head = new Node(item); } else { Node temp = head; while(temp.next != null) temp = temp.next; Node node = new Node(item); temp.next = node; } } /* (non-Javadoc) * @see java.lang.Iterable#iterator() */ public Iterator iterator() { return…

Linked lists are preferable over arrays when:

a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

c) you don't need random access to any elements

d) you want to be able to insert items in the middle of the list (such as a priority queue)

Arrays are preferable when:

a) you need indexed/random access to elements

b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.