Linked Lists (Single, Double, and Circular)

Linked Lists

Preface

This is a 2nd Quarter Assignment.


After you have completed the project listed at the end of this assignment, we will have an exam on Linked Lists. Therefore, it is essential that you do the work for this project by yourself and not copy code from the internet, another classmate, or anywhere else.

Overview of Linked Lists

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.

Another disadvantage is that a linked list uses more memory compare with an array - we need an extra 8 bytes (on 64-bit CPU) to store a reference to the next node.

Types of Linked Lists

The following diagram (taken from Wikimedia) shows a singly linked list with three pieces of data. Not shown is a separate pointer, called the head pointer, which points to the first element on the list.

File:Singly-linked-list.svg

doubly linked list is a list that has two references, one to the next node and another to previous node. The following diagram (also taken from Wikimedia) shows a doubly linked list with the same three pieces of data.

File:Doubly-linked-list.svg


Another important type of a linked list is called a circular linked list where last node of the list points back to the first node (or the head) of the list.

File:Circularly-linked-list.svg

Video Presentation on Linked Lists



Java's Standard Linked List Class

Read the following documentation and focus on understanding the built-in methods in the standard Java LinkedList class:

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html