Blogs

Featured Create an Ad

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

View All

Random Blogs

  • Learning and teaching online

    Posted August 21, 2016

    There are numerous definitions of online learning in the literature, definitions that reflect the diversity of practice and associated technologies. Carliner (1999) defines online learning as educational material that is presented on a computer. Khan (1997) defines onli...

  • 5 best online sources for free college textbooks

    Posted December 24, 2017

    It's no news that college textbooks do not come cheap. While grappling with tuition fees and living expenses, as a student, you also have to deal with the financial reality of buying textbooks. Online sites like Amazon and Chegg have become cheaper alternatives, but e...

  • Effective teaching strategies: Towards student-centred learning

    Posted July 1, 2018

    There are various teaching strategies that can enhance learning, but the broad list is mainly divided into teacher-centred and student-centred learning. The former is a teaching method that puts the teacher at the fore of the teaching process. The latter presupposes a t...

  • Scope and prevalence of suicide in Nigeria from a psychological perspective

    Posted Jan 31

    Abstract The rate of suicide in Nigeria is alarming. There is comorbidity between suicide, personality disorders, depression and addiction. Suicide is common among young adults and adolescents. This write up explores the meaning of suicide, factors influencing it, it's...

View All