List data structure

1. List Data StructureList Data Structure

2. What is List?What is List?
A list is a sequential data A list is a sequential data
structure. structure.
It differs from the stack and It differs from the stack and
queue data, structures in that queue data, structures in that
additions and removals can be additions and removals can be
made at any position in the list.made at any position in the list.

3. List operationsList operations
AddAdd : adds a new node: adds a new node
SetSet : update the contents of a : update the contents of a
nodenode
RemoveRemove: removes a node: removes a node
IsEmptyIsEmpty: reports whether the list is : reports whether the list is
emptyempty
IsFullIsFull: reports whether the list is : reports whether the list is
fullfull
InitializeInitialize: creates/initializes the list: creates/initializes the list
DestroyDestroy: deletes the contents of the : deletes the contents of the
list (may be implemented by re-list (may be implemented by re-
initializing the list)initializing the list)

4. Illustration/exampleIllustration/example
Initialize(L)Initialize(L)
Create a new empty List named LCreate a new empty List named L
Add(1,X,L)Add(1,X,L)
adds the value X to list L at position 1 (the start of the list adds the value X to list L at position 1 (the start of the list
is position 0), shifting subsequent elements upis position 0), shifting subsequent elements up
Set(2,Z,L)Set(2,Z,L)updates the values at position 2 to be Zupdates the values at position 2 to be Z
Remove(Z,L)Remove(Z,L)removes the node with value Zremoves the node with value Z
Get(2,L)Get(2,L) returns the value of the third node, i.e. Creturns the value of the third node, i.e. C
IndexOf(X,L)IndexOf(X,L)
returns the index of the node with value X, i.e. 1returns the index of the node with value X, i.e. 1

5. Illustration/exampleIllustration/example
OperationOperation List’s contentsReturn value
1. Initialiaze(L)<empty> -
2. Add(0,A,L) A -
3. Add(0,B,L) B A -
4. Add(1,C,L) B C A -
5. Set(1,N,L) B N A -
6. Add(1,D,L) B D N A -
7. Remove(A,L) B D N A
8. Set(3,I,L) B D N I -
9. Remove(D,L) B N I D
10. Remove(N,L)B I N

6. Exercise: List OperationExercise: List Operation
What would the contents of a list be after the following What would the contents of a list be after the following
operations?operations?
Initialise(L)Initialise(L)
Add(0,A,L)Add(0,A,L)
Add(0,F,L)Add(0,F,L)
Add(1,X,L)Add(1,X,L)
Add(1,G,L)Add(1,G,L)
Add(3,P,L)Add(3,P,L)
Add(2,V,L)Add(2,V,L)
Set(3,K,L)Set(3,K,L)
Set(0,H,L)Set(0,H,L)
Remove(V,L)Remove(V,L)
Remove(P,L)Remove(P,L)
 H G K AH G K A
What values would be returned by the following What values would be returned by the following
operations?operations?
IndexOf(A,L)IndexOf(A,L)
IndexOf(H,L)IndexOf(H,L)
Get(3,L)Get(3,L)

7. Storing a list in a static data Storing a list in a static data
structure (Array List)structure (Array List)
 This implementation stores the list in an array. This implementation stores the list in an array.
 The position of each element is given by an index The position of each element is given by an index
from 0 to n-1, where n is the number of elements.from 0 to n-1, where n is the number of elements.
 Given any index, the element with that index can Given any index, the element with that index can
be accessed in constant time – i.e. the time to be accessed in constant time – i.e. the time to
access does not depend on the size of the list.access does not depend on the size of the list.
 To add an element at the end of the list, the time To add an element at the end of the list, the time
taken does not depend on the size of the list. taken does not depend on the size of the list.
However, the time taken to add an element at However, the time taken to add an element at
any other point in the list does depend on the size any other point in the list does depend on the size
of the list, as all subsequent elements must be of the list, as all subsequent elements must be
shifted up. Additions near the start of the list take shifted up. Additions near the start of the list take
longer than additions near the middle or end.longer than additions near the middle or end.
 When an element is removed, subsequent When an element is removed, subsequent
elements must be shifted down, so removals near elements must be shifted down, so removals near
the start of the list take longer than removals near the start of the list take longer than removals near
the middle or end.the middle or end.

8. Storing a list in a dynamic data Storing a list in a dynamic data
structure (Linked List)structure (Linked List)
 The Link List is stored as a sequence of linked nodes.The Link List is stored as a sequence of linked nodes.
 As in the case of the stack and the queue, each node in a As in the case of the stack and the queue, each node in a
linked list contains data AND a reference to the next node.linked list contains data AND a reference to the next node.
 The list can grow and shrink as neededThe list can grow and shrink as needed
 The position of each element is given by an index from 0 to The position of each element is given by an index from 0 to
n-1, where n is the number of elements.n-1, where n is the number of elements.
 Given any index, the time taken to access an element with Given any index, the time taken to access an element with
that index depends on the index. This is because each that index depends on the index. This is because each
element of the list must be traversed until the required index is element of the list must be traversed until the required index is
found.found.
 The time taken to add an element at any point in the list does The time taken to add an element at any point in the list does
not depend on the size of the list, as no shifts are required. It not depend on the size of the list, as no shifts are required. It
does, however, depend on the index. Additions near the end does, however, depend on the index. Additions near the end
of the list take longer than additions near the middle or start. of the list take longer than additions near the middle or start.
The same applies to the time taken to remove an element.The same applies to the time taken to remove an element.
 The first node is accessed using the name LinkedList.Head
 Its data is accessed using LinkedList.Head.DataItem
 The second node is accessed using
LinkedList.Head.NextNode

9. Adding a node Adding a node
The new node is to be added at a specified index in the listThe new node is to be added at a specified index in the list
A special case is that the A special case is that the list is emptylist is empty. In this case, the first . In this case, the first
node is set to be the new node.node is set to be the new node.
Another special case is that the specified index is 0 (the
node is to be added at the front of the list).

10. Adding a node (2)Adding a node (2)
In the general case, an object reference Probe moves In the general case, an object reference Probe moves
through the list until the nodethrough the list until the node
before the required index is reached. Here, the node is to be before the required index is reached. Here, the node is to be
added at index 2.added at index 2.
If the new node is to be added at the end of the list, then the
NextNode of the last element is set to refer to the new
node.

11. Adding a node (3)Adding a node (3)
A possible algorithm (pseudocode) for the Add operationA possible algorithm (pseudocode) for the Add operation
AddAdd(index, Data, LinkedList)(index, Data, LinkedList)
Declare NewNode and initialise NewNode.DataItem with dataDeclare NewNode and initialise NewNode.DataItem with data
If(List.isEmpty)If(List.isEmpty)
Set NewNode.NextNode to NULLSet NewNode.NextNode to NULL
Copy NewNode to LinkedList.HeadCopy NewNode to LinkedList.Head
ElseElse
If (index is 0)If (index is 0)
Copy LinkedList.Head to NewNode.NextNodeCopy LinkedList.Head to NewNode.NextNode
Copy NewNode to LinkedList.HeadCopy NewNode to LinkedList.Head
ElseElse
Copy LinkedList.Head to ProbeCopy LinkedList.Head to Probe
i = 0i = 0
While i < index-1 And end of list not reachedWhile i < index-1 And end of list not reached
Copy Probe.NextNode to ProbeCopy Probe.NextNode to Probe
Increment iIncrement i
End WhileEnd While
Copy Probe.NextNode to NewNode.NextNodeCopy Probe.NextNode to NewNode.NextNode
Copy NewNode to Probe.NextNodeCopy NewNode to Probe.NextNode
End IfEnd If
End IfEnd If
Set NewNode to NULLSet NewNode to NULL
Set Probe to NULLSet Probe to NULL
Additional operations can also be implemented to add to the
beginning and end of the list.
AddFirst(Data, LinkedList) calls Add(0, Data, LinkedList)
AddLast(Data, LinkedList) calls Add(Size, LinkedList), where
Size is itself a call to the Size operation of the list.

12. Removing a nodeRemoving a node
A A TargetNodeTargetNode object is created. object is created.
There is a special case when There is a special case when TargetNodeTargetNode is equal to the first is equal to the first
node. In this case, LinkedList is set to point to the node. In this case, LinkedList is set to point to the
second node.second node.
In the general case, an object reference Probe moves
through the list until the required node is reached – at
each node the current node (Probe) is compared with
TargetNode.
A Previous object reference is also required to keep track of
the predecessor of the node to be removed. A special
case is when both references point to the same node –
this happens when the first node is to be deleted.
To delete the current node we can set Previous.NextNode to
be equal to Probe.NextNode.

13. Removing a node (2)Removing a node (2)

14. Accessing nodes (Get, Set, Accessing nodes (Get, Set,
IndexOf, View)IndexOf, View)
GetGet and and SetSet work in a similar way to work in a similar way to
AddAdd – Probe moves through the – Probe moves through the
list until the required list until the required indexindex is is
reached, and the reached, and the DataItemDataItem is is
returnedreturned ( (GetGet) or ) or updatedupdated ( (SetSet).).
IndexOfIndexOf works in a similar way to works in a similar way to
RemoveRemove – Probe moves through – Probe moves through
the list until the the list until the target nodetarget node is is
found, and returns the index. found, and returns the index.
ViewView – Probe moves through the list – Probe moves through the list
from beginning to end and the from beginning to end and the
DataItemDataItem is is returned returned at each node.at each node.

15. Variations on Linked ListsVariations on Linked Lists
Circularly linked listsCircularly linked lists
The tail of the list always points to the head of the listThe tail of the list always points to the head of the list
Doubly linked lists
These permit scanning or searching of the list in both
directions. (To go backwards in a simple list, it is
necessary to go back to the start and scan forwards.) In
this case, the node structure is altered to have two links:
Sorted lists
Lists can be designed to be maintained in a given order. In this
case, the Add method will search for the correct place in
the list to insert a new data item.

16. List ImplementationList Implementation

17. List Implementation in JavaList Implementation in Java
The Java Collections Framework in the most recent The Java Collections Framework in the most recent
version of Java now includes list classes. version of Java now includes list classes.
As you did for the stack & queue, you will create As you did for the stack & queue, you will create
your own List class in order to learn how a list is your own List class in order to learn how a list is
implemented. implemented.
Your class will again be a bit simpler than the Your class will again be a bit simpler than the
Collections Framework one but it will do essentially Collections Framework one but it will do essentially
the same jobthe same job
In this case you will look at Java implementations of In this case you will look at Java implementations of
an an ArrayListArrayList and a and a LinkedListLinkedList. Both lists have the . Both lists have the
same operations, so we can define a class same operations, so we can define a class ListList
which includes minimal implementations of the which includes minimal implementations of the
operations. The ArrayList and operations. The ArrayList and LinkedListLinkedList classes classes
will be subclasses of will be subclasses of ListList..
The List class will define the set of operations which The List class will define the set of operations which
a list class must have. This is sometimes known as a list class must have. This is sometimes known as
the interface of a list. Both kinds of list will have the the interface of a list. Both kinds of list will have the
same interface.same interface.

18. List Implementation in JavaList Implementation in Java
Notice that the LinkedList class makes use of Notice that the LinkedList class makes use of
a Node class which is exactly the same as a Node class which is exactly the same as
the one used for the dynamic queue.the one used for the dynamic queue.