Java Linked List

While we talk about linked lists in class, I wanted to go over why we talked about a first/header pointer at the beginning of the list but not a tail pointer (yet). We are discussing a stack, which follows the LIFO property (meaning Last In, First Out). The last thing entered into the stack becomes the first node. This means that we can only remove in constant time nodes from the front of the list (where the first/header pointer is). To remove from anywhere else in the list, we would have to traverse the list (through a while loop or recursion) and examine each node. This of course would be slower than constant time. Here is a video that discusses the linked list implementation in java.

Leave a Reply

Your email address will not be published. Required fields are marked *