Quick Index
Overview


In this section, we'll look at essential accessing methods such as "get", "first" and "last".

Here is a companion video for this section.

Method 'get'


From the ADT:

get(index);
	/*
	Return element at given index.
	If passed arg "index" is invalid, throws exception:
		"(get) Index %d is out of bounds"
	*/

We need to come up with an algorithm for getting an element (data) at a given index.

Try 1 - Algorithm
  • Start a count at 1
  • Move (navigate) down the list
  • Increment the count as we move from node to node
  • When count is equal to the specified index, we are done -- get the data from the given node, and return the data
Recall Linked List Concept Sketch
Note that in the context when coding linked list methods, we only have "firstNode" and "lastNode" ivars
Key Player: Node
Let's recall our buddy the node.

She has three components: nextNode, prevNode, and data.
Try 2 - Improved Algorithm
Given our review of linked list and node, we will add detail to our algorithm.

 given "index" (the pos to access)
count = 0
node = firstNode
While node is not null
	If (count equals index)
		Return the node's data
	node = node.getNextNode()
	Increment count
Handle Exception Cases
We would typically want to add exception handling code.

This is best to do at the top (even first step) of the algorithm. Something like:

  • Check if the given index is a valid index
  • If not valid, then we would then throw an exception, return null, etc (per the problem requirements)


Methods 'first' and 'last'


From the ADT:

first();
	/*
	Return first element
	If list is empty, throws exception:
		"(first) Attempted to access element in empty list"
	*/

last();
	/*
	Return last element
	If list is empty, throws exception:
		"(last) Attempted to access element in empty list"
	*/

We like easy logic. For each of these methods we'll simply call "get" with the appropriate first and last index.

And we don't want to forget to add the mentioned exception handling at the top of the methods.





























Data Structures And Algorithms (DSA) (Chapter 401 - Linked List Logic)










Chapter 401 - Linked List Logic Fundamental Accessing

Contents Intro OO Review Concepts Design Traversal Algorithms Memory

Chapter Top Search TOC