Lists Abstract Data Structure

Lists Abstract Data Structure

DataStructuresLinkedListofN

This article summarizes some of the main important points you need to know about lists

Description:

  • An abstract datatype represents and ordered sequences of value.
  • Same value can occur more than once
  • Each value is considered a distinct list value even if it is a duplicate value

Operation Performed on :

  • isEmpty() : testing whether or not a list is empty
  • isFull(): tests if the list is full, if it is limited (bounded) list
  • add(x) : appends an entity to a list in the provided, by i , index position
  • remove(i) : removes an entity from list positioned on i position

Implementations in Java:

It is a bit of overhead to list and describe all practical implementations of lists, for this a whole book or course will be need.

However I try to describe as much as I can in data structures section.

The two main approaches that lists are implemented in Java are:

Arrays:
  • The length of an array is established when the array is created
  • After creation, its length is fixed. (not entirely true)
  • Getting an element positioned on index i is O(1) constant time
  • Harder to resize, take O(n) liner time.

Linked Lists:

  • Unknown size at creation time (can be fixed if need)
  • Length is dynamically resided
  • Getting element positioned on index i is liner O(n)
  • Resize takes constant time O(1)
  • Inserting element in front, end, or middle takes constant time O(1)

 

 

 

Facebooktwittergoogle_pluslinkedinFacebooktwittergoogle_pluslinkedin

Leave a Comment