Blogs

Data structure and algorithm: An introduction to ArrayList and LinkedList

  • When we talk about data structure and algorithm in programming, we are simply talking about how programs are being written by programmers on how devices’ data supposed to behave in different circumstances. Those data could either be input gotten from the users or data put by programmers during program development. And algorithms, on the other hand, are the step by step approach on how those programs are going to function from start to finish bearing in mind the efficiency and the effectiveness of the process down to the final result. Now, this data, as we all know, is just information that could be anything. Always a programmer decides what data is, based on the demand at hand and what he/she wants to achieve with the program. Therefore, based on that knowledge, the right tools to be used are at the forefront of the programmer’s plan and decision. This is where data structure and algorithm come into play. As we have so many of them (data structures), one has to really get conversant with them to be able to know the right one to use when the need arises. Therefore, against this background, in this article, we are going to look at ArrayList and LinkedList as they are some of the most popular forms of data structure that programmers used across the board.

    By the way, this is not the first time we talk about data structure and algorithm, in my last article, we also talked about another form of data structure, arrays – also, one of the most highly used data structures by programmers all over the globe - and binary search algorithm was also discussed. You can look at the article here.

    What is ArrayList?

    ArrayList is a re-sizeable array. It is one of the classes that implement the Java List interface of Java collection framework. ArrayList presents a more flexible and robust form of array that so many programmers prefer to use in place of an actual array because it allows the flexibility programs required, most especially, programs that have a lot of manipulations to deal with. It can be shrunk or be expanded; all depends on what you do with it or what instructions it is implementing. Although, an ArrayList has all these advantages over array, its relatively slower than array when it comes to implementation, perhaps because of all the work it’s capable of doing.

    How to create ArrayList

    You can create ArrayList by first of all mentioning the word, ArrayList then followed by specifying the kind of data (Integer, Double e.t.c) you intend to store in it in between two angle brackets. Then followed by the variable name (the name of the new ArrayList you’re creating). But it is important to know that, ArrayList doesn’t accept primitive data type. It instead uses corresponding wrapper class for those kinds of data type. Example, instead of int, it accepts Integer, Double is used in place of double and so on.

    To create a new ArrayList, the keyword ‘new’ has to be mentioned then followed by the word ArrayList and again followed by the type of data (wrapper class data) to be stored in between angle bracket. At this point you can choose to either give the initial size of the items or elements that this ArrayList is going to hold, or an automatic size will be assigned. The default size of ArrayList is ten (10).

    An important point to note that though, after creating the ArrayList skeleton, its library must be imported before it can function. You can do that by clicking at the control key together with the space key on your computer (Ctrl+Space).

    Example of import statement and the ArrayList being created are:

    Looking at the source code of the above ArrayList created, one thing that is missing is that no size value was given to it. This means that this ArrayList will have a default size, which is ten (10) as we stated earlier. But it can be increased as more and more elements are added to it since ArrayList is dynamic in nature. Likewise, the size can be decreased if we choose to reduce the number of elements in the list.

    Adding values to ArrayList

    To add value(s) to ArrayList, the name of the ArrayList must be stated, followed by the dot notation then the word ‘add’ should follow. And right in front of the word ‘add’, a bracket, containing the element being added will follow suit. Example is here below:

    The above code shows how you can add elements to ArrayList. The elements will be arranged chronologically as they enter when this ‘add method’ is used. But, apart from adding at the very last of the list, you can also add at a specific position. All you need to do is adding the index in the parenthesis indicating where in the list you want to place the element. You can do that by separating them with a comma, and the index number comes first, then separated by comma, the element comes next. Here is an example:

    When you add a new element in the position of another element, the old element will shift to the next index. For example, in this case, the element in the index 10 will shift to index 11 and so on. This way, our list expands automatically. Remember, this is one of the beauties of ArrayList, its ability to expand anytime!

    Displaying the ArrayList elements

    To display ArrayList elements, just like an array, you can display an individual member or the whole of the content. To display any member, just mention the ArrayList, then dot (.) and the word ‘get’ comes right afterwards. After the word ‘get’, then, put, inside a bracket, the index number of the item you intend to get. While on the other hand, if you want to display them all, then that should be done with the help of a loop.

    Example: To get any element from the list

    The output:

    Example: To display all the elements

    The output:

    Removing some elements in the list

    It’s pretty simple to remove an element from an ArrayList. All you need to do is to mention the variable name plus dot (.) and the word ‘remove’, then as always, the index number has to be mentioned in between bracket. Period! When you run the program, the element will go. Let see it in display below:

    Then, let's write the code to display the new list below and see what we are left with.

    The output:

    Notice, the first and the last elements that we displayed earlier have gone.

    LinkedList:  What is it and what are its commonly used methods

    LinkedList is a linear data structure that has what is referred to as nodes. Each node is located separately in a device memory and it consists of two parts, a data field that could contain any data (element) stores in it based on the given wrapper class, and a reference to the next node. it’s also important to know that LinkedList also implements Java List interface class just like ArrayList. But unlike array and ArrayList, LinkedList elements are not stored in contiguous memory location. Meaning, each node is separate from each other; they are not stored right after each other in the computer memory, as mentioned earlier. They are only linked through some sort of pointer.

    The first node is called head, and it gets linked to the next node by a linking mechanism in the memory. The process continues until the last node, which is called the tail, and always, the tail node points to a null node. Null node means that there’s no more node to point at in the list. This is generally what is all about a basic LinkedList.

    Below is a graphical representation of the above explanation for easy processing.

    Basically, we have three types of LinkedList. They are, singly LinkedList, doubly LinkedList and circular linkedLists. You can check this article for more about the types of LinkedList.

    Creating an object of LinkedList

    Adding elements to LinkedList

    To add element (s) into an empty LinkedList object, the name of the object has to be mentioned first, then followed by the dot (.), then the word ‘add’ should follow with a bracket right in front of it, just as in the case of ArrayList. Below is a source code to illustrate how it’s done:

    Displaying the elements in the list

    To display the elements in the list, one can either access an element through its index or just write the object name in a print statement in order to print them all. And to access an element by its index, there are several ways to achieve this, some of which are shown in the below source code:

    The output

    To display all the elements in the list, here is the source code below:

    The output

    Note, you can also, use loop to access and display them, one each in a separate line.  Here is how:

    The output

    Some other commonly used methods in LinkedList are below contained in the source code. With each preceded by a comment to explain what it does. Here you go:

    Output 

    Notice, the first element has gone after we used ‘remove method’. And after using ‘set method’, the last element has changed to “Hanne” instead of “Karime” that was previously in our list.  

    Finally, don’t forget to practice, practice and keep practising. That’s how you become a better programmer. That’s all we are able to bring to you regarding ArrayList and LinkedList in our data structures and algorithm series. Indeed, there’s much more to these data structures. I encourage you to explore out there. And, lets I forget, I’d like to hear what you think about this article in the comment section below. Until then, happy coding! 

    Written by Rahmatu Lawan from Yanbu, Saudi Arabia

No Stickers to Show

X

Recent Blogs

  • Bachelors and masters scholarships at Bocconi University

    Posted Oct 10

    Bocconi University is a private university in Milan, Italy. Bocconi provides undergraduate, graduate and post-graduate education in the fields of economics, management, finance, law, political science, and public administration. SDA Bocconi, the university's business sc...

  • Radboud University offers masters scholarships

    Posted Oct 10

    Radboud University is a public university with a strong focus on research located in Nijmegen, the Netherlands. It was established on 17 October 1923 and is situated in the oldest city of the Netherlands. The RU has seven faculties and enrolls over 22,000 students. The...

  • Reasons why Information Systems should be integrated into every business

    Posted Oct 8

    Is it any wonder that in today’s world knowledge of computers/technologies is becoming so invaluable? It is evidently clear that almost all businesses are either having a dot com address, meaning are having a website of their own, or they are enjoying/relying on s...

  • Bachelors and masters scholarships are being offered at the University of Bristol

    Posted Oct 5

    The University of Bristol is a red brick research university in Bristol, England. It received its royal charter in 1909, although it can trace its roots to a Merchant Venturers' school founded in 1595 and University College, Bristol, which had been in existence since 18...

View All

Random Blogs

  • 8 effective ways to be an A-student

    Posted June 12, 2017

    You know those students. The A-grade ones that get the top marks, has impeccable attendance, and always seem to be one step ahead of everyone? Well, it turns out that even though they may have learning abilities different from everyone, there are certain habits and char...

  • Migraine – causes, symptoms and remedies

    Posted September 9, 2018

    Simply put, migraine is a specific kind of a headache. The term migraine emanates from an old French word, megrim, which refers to a syndrome of dizziness, head pain, and nausea. It eventually became known as a migraine and people who get them are called migraineurs. I...

  • Exploring possibilities in academia: A discussion paper on professional development

    Posted Apr 5

    I was invited recently by a group of young Nigerian entrepreneurs to give a talk on professional development, I supposed, aimed at providing a guide for the bright minds in their adventure and search for opportunities after graduation. I’d like to thank Maryam Abd...

  • Should we replace textbooks with tablets?

    Posted August 3, 2017

    Along with the development of technology, tablets have taken over laptops and computers. The convenience associated with tablets has made it possible to be used as textbooks. Before introducing tablets to play the role of textbooks, it is important to take a look at the...

View All