CS2040: List ADT and Linked Lists

Use of a List

- Keep the same type(class) in a list

- Manage our data

ADT of a List

- A dynamic linear data structure

- Accessible one after another starting from the head

e.g: Create empty list, check if list is empty, add item at certain position

Sample:

ADT: A contract, ie an interface

Implementation: Arrays, linked list

NOTE: <List> is an interface

List implementation in Array

For insertion,

1. Shift right

2. Add

3. Update nodes

For Deletion,

1. Close Gap

2. Update the nodes

However, we want to think about the efficiency of this operation.

When we shift, it is doing the operation in N time.

Space Efficiency as well, we don't know the MAXSIZE ahead of time.

An array is good in a fixed size list but for variable size, a linked list is better

List implementation in Linked List

Instead of having unuse spaces like array, we can just insert and redirect the memory for linked list.

If we want to remove, just redirect the memory to the next linked node, ignoring the previous node that was linked, this gives the illusion of a "remove"

This works the same as object references.

Object references:

When a new data type is declared, draw another box.

Strings are stored as individual characters.

Primitive data types do not create new boxes

List Node:

List node with generics:

Each node will contain the data and the next node.

e.g

ListNode <String> node3 = new ListNode <String>(“a3”,null);ListNode <String> node2 = new ListNode <String>(“a2”,node3);ListNode <String> node1 = new ListNode <String>(“a1”,node2);ListNode <String> head = new ListNode <String>(“a0”,node1); 

ADT Linked List

Instead of the prev code we can do as follows:
LinkedList <String> list = new LinkedList <String> ();
list.addFirst(“a3”);

list.addFirst(“a2”);

list.addFirst(“a1”);
list.addFirst(“a0”) 

Don't need to worry about how addFirst is implemented.

Interface:

Implementation:

Using it to define basic linked list

The head is a listnode object which contains the element variable

Add and remove the first implementation

add first just creates the new node and changes the head.

Then it increases the number of nodes overall.

Removefirst copies the current head and sets the current head to the next one.

It then decreases overall number of nodes

then returns the prev head which it has copied.

Taken from Lecture 6

<Prev  ADT                                                Next Pt2>