The List ADT (series)

Olaoluwa Oke| 4 February 2024

Welcome welcome welcome to the first episode of the List series, Where we will be talking about the List Abstract Data type, from data data Structures that implement the List ADT to writing them ourselves

I will try my best not to miss any point, chances are if you are reading this, You know me and just text me or call me and we will figure it out together, You are probably already like "Can this guy just stfu and let's get to the List ADT you promised me" hey, my bad let's get it

Honestly, I believe we all have an intuitive understanding of what a list is already ( if you don't, chances are English is not your first language). We just want to turn this "intuitive understanding" into a concrete data structure,

just in case - A list is a number of items written consecutively, one after the other, or below another, for example Grocery List , song Playlist(this one even has a list in the name), A list of people that have offended you ( abeg now, forgive them)

Technically, A list is said to be a finite, ordered sequence of data items known as elements - close to the definition of a sequence in mathematics

finite - having limits or bounds i.e We know the end

The most important concept in the list is positions, In order words we perceive a list to have a first element, a second ........ n -1, n elements ( n being the last element);

“Ordered” in this definition means that each element has a position in the list. So the term “ordered” in this context does not mean that the list elements are sorted by value. (Of course, we can always choose to sort the elements on the list if we want; it’s just that keeping the elements sorted is not an inherent property of being a list.)

now let's go a little deeper -That was what she said

Each list must have some data type, you do not put a podcast in a music playlist, hey now you can, if you're a pychopath

In this series, we will be using Java generics, so go get your knowledge up!, so in a list, all elements of the list are usually assumed to have the same data type, although there is no conceptual objection to lists whose elements have differing data types if the application requires it.

A list is said to be empty when it contains no elements. The number of elements currently stored is called the length of the list. The beginning of the list is called the head , the end of the list is called the tail . (reference)

but before we go ahead talking about lists, let's talk about the List ADT

The List ADT

What is an interface ?

Quick Story
I was talking to a friend about how you can buy jollof Rice in a Nigerian Domino pizza, you laugh but it's true, You can have fried plantain as a topping, you also laugh but it's true (somewhat)

Now Dominos as we know , is a Franchise, also 7Eleven that when you want to open a 7Eleven anywhere in the world ( don't fact-check me on this please )

You will have to make an application to 7eleven about this, after they review it and you are approved, They send you a contract of what your 7eleven must do, Which as we all know food-wise, You must -

sellPizza(); sellTobaccoAndCigarettes(); sellSlurpee(); sellBusTickets(); sellWings(); keepTheFranchiseName();

Now as a prospective 7eleven owner, there are other guidelines obviously, this is just very high-level representation, you must implement all these, and you must follow that contract, now if you want, in your own 7 eleven you can decide to

sellFuel(); sellCoffee(); sellExpiredDrinks(); -- just joking just joking

but you must first obey the contract or else no agreement

so an interface a defines a contract that classes must adhere to when they implement the interface. Interfaces in Java are used to achieve abstraction and provide a way to achieve multiple inheritance since a class can implement multiple interfaces.

Let's create out List ADT(Franchise) using an interface

A list should be able to -

- To grow and shrink in size as we insert and remove elements. - We should be able to insert and remove elements from anywhere in the list. ; - We should be able to gain access to any element’s value, either to read it or to change it. - We must be able to create and clear (or reinitialize) lists. It is also convenient to access the next or previous element from the “current” one.

Let's Write code for our List ADt using an interface - in generics

// List class ADT. Generalize the element type using Java Generics.
public interface List<E> { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(E it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(E it);

  // Remove and return the current element
  public E remove() throws NoSuchElementException;

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at the beginning
  public void prev();

  // Move the current position one step right, no change if already at the end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if the current position is at the end of the list
  public boolean isAtEnd();

  // Return the current element
  public E getValue() throws NoSuchElementException;

  // Tell if the list is empty or not
  public boolean isEmpty();
}

Keep this contract if you want to join our List franchise, You must have all these methods in your class before you can start

class MyNewList<E> implements List<E> {
// must have all the methods implemented here
}

We're hitting the pause button on our List adventure for today. Next episode , we'll talk about Positions in Lists Thanks a bunch for hanging out in this episode of the List series.

via GIPHY