Lets Learn Lists!! | Learning Data Structures with CompAndCode #1





Introduction:


Seeing as TheNibbleByte have an audience of GCSE students, A Level students and maybe some degree students, I thought that it would be beneficial to talk about Data Structures, given that this is often a challenging area of the syllabus.


Definition:


A Data Structure is a 'specialised format for organising, processing, retrieving and storing data'. They can be categorised into 'linear' and 'non linear' (more on that in future posts!!!


Theory:



  • A list is simply a collection of elements in which the same element may appear multiple times.

  • They can be either static (using arrays) or dynamic.

  • They are mutable, allowing their contents to change (see the operations below!).

  • [] are used to represent a list, with elements inside, separated by commas.


List Operations:

isEmpty() - Tests if the list is empty, returning a boolean (True/False).

append(item) - Adds a new item to the end of the list.

remove(item) - Removes the first occourance of an item, from the list.

search(item) - Tries to find the item in the list, returning a boolean (True/False).

length(item) - Returns the number of items in a list, int.

index(item) - Returns the position of an item in the list.

insert(pos,item) - Inserts a new item in the list, at that position.

pop() - Removes and returns the last item in the list.

pop(pos) - Removes and returns the item at the specified position.


Representing Lists Using Arrays:

We haven't yet talked about Arrays (that will happen in the next few weeks) but an Array is 'a finite, ordered set of elements'.

Useful if the maximum number of elements is known in advance.


Implementation in Python and Java:

Python:

Most of the methods for lists are built in however I did have to build a couple myself.


Java:

Most of the methods are built in which makes things easy.