The linked list ADT

The Linked List ADT is very much like the node$-$based Queue ADT we studied in class. The $\_\_$init$\_\_()$

operation is as follows:

class LList $($ object $)$:

def $\_\_$init$\_\_($ self $)$:

$"""$

Purpose

creates an empty list

$"""$

self $.\_$size $=0$ # how many elements in the stack

self $.\_$head $=$ None # the node chain starts here ; initially empty

self $.\_$tail $=$ None

A linked list is an object with the following attributes:

size This keeps track of how many values are in the list.

head This is a reference to the first node in the node chain. An empty Linked List has no node chain, which

we represent with None.

tail This is a reference to the last node in the chain. If the list is empty, this is None.

Notice that the LList attributes are protected. This helps us write test cases that would not be possible with

private attributes. Also note that the node class attributes are public. This makes their use in the LList class

a little easier. We no longer need to use the setters and getters from Chapter $14,$ in which the attributes

were private.