Part 16: LinkedList in Java with real time examples

JAVA | 104 comments

LinkedList in Java

Linked List is almost similar ArrayList features. It is a part of the collection framework present in java.util package. The class is an implementation of the linear LinkedList data structure. Here the elements are not stored in adjoining locations and every element is an isolated object with a data part and address part. Here the elements are linked or connected using pointers and addresses. Each element is known as a node but these nodes are not directly used. In case the dynamicity and ease of insertions and deletions, they are preferred over the arrays.

Example: The following implementation demonstrates how to create and use a linked list. The LinkedList class is almost identical to the ArrayList:

Example 1

import java.util.LinkedList; // Import the LinkedList class

public class Main {

public static void main(String[] args) {

LinkedList<String> letters= new LinkedList<String>();

letters.add("A");

letters.add("B");

letters.add("C");

letters.add("D");

System.out.println(letters);

// Adding elements to the linked list

letters.add("AA");

letters.add("BB");

letters.addLast("CC");

letters.addFirst("DD");

letters.add(2, "EE");

System.out.println(letters);

letters.remove("B");

letters.remove(3);
letters.removeFirst();
letters.removeLast();
System.out.println(letters);
}
}

OUTPUT
A,B,C,D
[DD, AA, EE, BB, CC]
[AA]

In the example 1 java code we use Add, Remove etc. Operations on the code and these operation details given below: linkedList

  1. Add Elements: In order to add an element to an ArrayList, we can use the add() method. This method is overloaded to perform multiple operations based on different parameters.
  • addFirst():Adds an item to the beginning of the list.
  • addLast():Add an item to the end of the list.
  • removeFirst():Remove an item from the beginning of the list.
  • removeLast():Remove an item from the end of the list.
  • getFirst():Get the item at the beginning of the list.
  • getLast():Get the item at the end of the list.
  • add(Object): It is used to add an element at the end of the LinkedList.
  • add(int index, Object): This method is used to add an element at a definite index in the LinkedList.
  1. Changing Elements: After adding the elements, if we wish to change the element, it can be done by the set() method. Since a LinkedList is indexed, the element which we wish to change is referenced by the index of the element. Therefore, this method takes an index and the updated element needs to be inserted at that index.
  2. Removing Elements: In order to remove an element from a LinkedList, we can use the remove() method. This method is overloaded to perform multiple operations based on different parameters. They are:
  • remove(Object): This method is used to remove an object from the LinkedList. If there are multiple such objects, then the first incidence of the object is removed.
  • remove(int index): LinkedList is indexed, the method takes an integer value simply removes the element present at that specific index in the LinkedList. After removing the element, all the elements are moved to the left to fill the space and the indices of the objects are updated.
  1. Iterating the LinkedList: There are multiple ways to iterate through the LinkedList. The most famous ways are by using the basic for loop in combination with a get() method to get the element at a specific index and the advanced for loop.

A Java program to iterate the elements in an LinkedList given below:

import java.util.*;

public class ExMain {

public static void main(String args[])

{

LinkedList<String> letters  = new LinkedList<>();

letters.add("Md");

letters.add("Harun");

letters.add(1, "is");

// Using the Get method and the for loop

for (int i = 0; i < letters.size(); i++) {

System.out.print(letters.get(i) + " ");

}

System.out.println();

// Using the for each loop

for (String str : letters)

System.out.print(str + " ");

}

}

Output:

Md is Harun
Md is Harun

How LinkedList work?

LinkedList pretend as a dynamic array and no need to specify the size while creating it, the size of the list auto increases when  dynamically add and remove the items. In addition to, the elements are not stored in a constantly. So, there is no need to increase the size. Internally, the LinkedList is implemented using the doubly linked list data structure. The main difference between a normal linked list and a doubly  LinkedList is that a doubly linked list contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.

LinkedList Constructors :

To create a LinkedList create an object of the LinkedList class. The LinkedList class consists of various constructors that allow the possible creation of the list. The following are the constructors available in this class:

LinkedList(): This is for creating an empty linked list. If  create an empty LinkedList with the name letters, then, it can be created as:

LinkedList letters = new LinkedList();

LinkedList(Collection C): This constructor is used to create an ordered list which contains all the elements of a specified collection, as returned by the collection’s iterator. If we wish to create a linkedlist with the name letters, then, it can be created as:

LinkedList letters = new LinkedList(C);

Java LinkedList class hierarchy:

The Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.

The important points about Java LinkedList are:

  • It can contain duplicate elements.
  • LinkedList class maintains insertion order.
  • The clss is non synchronized.
  • The class manipulation is fast because no shifting needs to occur.
  • This class can be used as a list, stack or queue.

Hierarchy of LinkedList class:

Doubly Linked List: In the case of a doubly linked list, we can add or remove elements from both sides. java LinkedList class using doubly linked list

LinkedList class declaration with java.util.LinkedList class.

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

Constructors of Java LinkedList

LinkedList(): It is used to construct an empty list.

LinkedList(Collection<? extends E> c): It is used to construct a list containing the elements of the specified collection, in the order, they are returned by the collection’s iterator.

Methods of Java LinkedList

boolean add(E e):This method is used to append the specified element to the end of a list.

void add(int index, E element):This methodis used to insert the specified element at the specified position index in a list.

boolean addAll(Collection<? extends E> c):This method is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.

boolean addAll(Collection<? extends E> c):This method is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.

boolean addAll(int index, Collection<? extends E> c):This method is used to append all the elements in the specified collection, starting at the specified position of the list.

void addFirst(E e):This method is used to insert the given element at the beginning of a list.

void addLast(E e):This method is used to append the given element to the end of a list.

void clear():This methodis used to remove all the elements from a list.

Object clone():This method is used to return a shallow copy of an ArrayList.

boolean contains(Object o):This method is used to return true if a list contains a specified element.

Iterator<E> descendingIterator():This method is used to return an iterator over the elements in a deque in reverse sequential order.

E element():This method is used to retrieve the first element of a list.

E get(int index): This method is used to return the element at the specified position in a list.

E getFirst(): This method is used to return the first element in a list.

E getLast(): This method is used to return the last element in a list.

int indexOf(Object o): This method is used to return the index in a list of the first occurrence of the specified element, or -1 if the list does not contain any element.

int lastIndexOf(Object o):This method is used to return the index in a list of the last occurrence of the specified element, or -1 if the list does not contain any element.

ListIterator<E> listIterator(int index):This method is used to return a list-iterator of the elements in proper sequence, starting at the specified position in the list.

boolean offerFirst(E e): This method inserts the specified element at the front of a list.

boolean offerLast(E e): This method inserts the specified element at the end of a list.

E peek(): This method is retrieves the first element of a list

E peekFirst(): It retrieves the first element of a list or returns null if a list is empty.

E peekLast(): It retrieves the last element of a list or returns null if a list is empty.

int size(): This method is used to return the number of elements in a list.

A common topic on ArrayList vs. LinkedList

  • The LinkedList class is a collection which can contain many objects of the same type, just like the ArrayList.
  • The LinkedList class has all of the same methods as the ArrayList class because they both implement the List interface. This means that you can add items, change items, remove items and clear the list in the same way. While, the ArrayList class and the LinkedList class can be used in the same way, they are built very differently.

How the ArrayList AND LinkedListworks:

The ArrayList class has a regular array inside it. When an element is added, it is placed into the array. If the array is not big enough, a new, larger array is created to replace the old one and the old one is removed. on the other hand, how the LinkedList works: Previously we have discussed about it. The LinkedList stores its items in “containers.” The list has a link to the first container and each container has a link to the next container in the list. To add an element to the list, the element is placed into a new container and that container is linked to one of the other containers in the list.

When To Use
When you want to access random items frequently use an ArrayList. You only need to add or remove elements at the end of the list. Besides, It is best to use a LinkedList when only use the list by looping through it instead of accessing random items. when frequently need to add and remove items from the beginning, middle or end of the list.

Chapter 6: Software Testing with example Process

What is Testing? Testing is the process of evaluating a system or its component(s) with the intent to find whether it satisfies the specified requirements or not. In simple words, testing is executing a system in order to identify any gaps, errors, or missing...

Chapter – 4: Project management with Example Procedures.

Project management Software project management is an essential part of software engineering. Projects need to be managed because professional software engineering is always subject to organizational budget and schedule constraints. The project manager‘s job is to...

You may find interest following article

Chapter 6: Software Testing with example Process

What is Testing? Testing is the process of evaluating a system or its component(s) with the intent to find whether it satisfies the specified requirements or not. In simple words, testing is executing a system in order to identify any gaps, errors, or missing requirements in contrary to the actual requirements. According to ANSI/IEEE 1059 standard, Testing can be...

Chapter-5: Cost Estimation Tutorial in Software Engineering

Cost Estimation Tutorial Cost is s strategic concept in software development for the following reasons: Project management: Estimating cost is extremely crucial in carrying out project management activities such as scheduling, planning and control.Feasibility Study: Making investment decisions regarding software projects requires full cost breakdown and analysis...

Chapter – 4: Project management with Example Procedures.

Project management Software project management is an essential part of software engineering. Projects need to be managed because professional software engineering is always subject to organizational budget and schedule constraints. The project manager‘s job is to ensure that the software project meets and overcomes these constraints as well as delivering...

Chapter -3: Agile Software Development Method Process

Agile Software Development Although there are many approaches to rapid software development, they share some fundamental characteristics: The processes of specification, design, and implementation are interleaved. There is no detailed system specification, and design documentation is minimized or generated automatically by the programming environment used to...

Chapter 2: Software processes with various model

Objectives: understand the concepts of software processes and software process models;have been introduced to three generic software process models and when they might be used;know about the fundamental process activities of software requirements engineering, software development, testing, and evolution;understand why processes should be organized to cope with...

Frequency Word for IELTS Listening

Frequency Word for IELTS Listening School a. Library  WordSentence1. Shelf 2. Librarian 3. The stacks 4. Return 5. Fine 6. Magazine 7. Copier  8. Overdue  9. Reading room  10. Reference room  11. Periodical room  12. Study lounge  13. Catalogue  14....

Chapter 8: Gantt chart Project Development in SDLC

Gantt chart Project DevelopmentSchedule (project management) The project scheduleis the tool that communicates what work needs to be performed, which resources of the organization will perform the work and the timeframes in which that work needs to be performed. The project scheduleshould reflect all of the work associated with delivering the project on time....

Chapter 7: Feasibility Analysis in Software Develoment Life Cycle.

Feasibility AnalysisWhat is Feasibility Analysis?? An analysisand evaluation of a proposed project to determine if it (1) is technically feasible, (2) is feasible within the estimated cost, and (3) will be profitable for Organization. Feasibility analysis guides the organization in determining whether to proceed with the project. Feasibility analysis also identifies...

Chapter 6: Data Flow Diagram in Software Development Life Cycle.

Data Flow Diagram What is DFD? A data flow diagram (DFD) is a graphical representation of the "flow" of data through an information system, modelling its process aspects.A DFD is often used as a preliminary step to create an overview of the system, which can later be elaborated.Show users how data moves between different processes in a system. Figure 1: DFD Symbols...

Chapter 5: System request on SDLC

System Request In most organizations, project initiation begins by preparing a  system request. A  system request is a document that describes the business reasons for building a system and the value that the system is expected to provide.The project sponsor usually completes this form as part of a formal system project selection process within the...

Chapter 4: SDLC design Phase

SDLC design Phase DFD (Design Analysis)Architectural DesignUI DesignDatabase DesignProgram DesignArchitectural design (logical)Network designClient –server designClient designServer designCloud ComputingDatabase designER diagramRelational diagramDDL (not now..!!)Program design (physical)Investigating the hardware/software platformPhysical DFDData storageData...

Chapter 3: SDLC and its Life cycle Phases.

What is SDLC? The systems development life cycle (SDLC), also referred to as the application development life-cycle, is a term used in systems engineering, information systems and software engineering to describe a process for planning, creating, testing, and deploying an information system. Career Paths for System Developers Systems Development Life Cycle Building...

Chapter 2: SDLC Key Features For SYSTEMS ANALYST.

Once upon a time, software development consisted of a programmer writing code to solve a problem or automate a procedure. Nowadays, systems are so big and complex that teams of architects, analysts, programmers, testers and users must work together to create the millions of lines of custom-written code that drive our enterprises.To manage this, a number of system...

Chapter 1: System analysis and Design Overview.

System analysis, a method of studying a system by examining its component parts and their interactions. •It provides a framework in which judgments of the experts in different fields can be combined to determine what must be done, and what is the best way to accomplish it in light of current and future needs.  •The system analyst (usually a software engineer or...

Chapter 4: Concept Of Sampling, Quantization And Resolutions

Concept Of Sampling, Quantization And Resolutions Conversion of analog signal to digital signal: The output of most of the image sensors is an analog signal, and we can not apply digital processing on it because we can not store it. We can not store it because it requires infinite memory to store a signal that can have infinite values. So we have to convert an...

Chapter 3: Images and Conversions in Digital Image Process

Images And Conversions There are many type of images, and we will look in detail about different types of images, and the color distribution in them. The binary image The binary image as it name states, contain only two pixel values. 0 and 1. In our previous tutorial of bits per pixel, we have explained this in detail about the representation of pixel values to...

Chapter 2: Concept of Pixel in Digital Image Process

Concept of Pixel Pixel Pixel is the smallest element of an image. Each pixel correspond to any one value. In an 8-bit gray scale image, the value of the pixel between 0 and 255. The value of a pixel at any point correspond to the intensity of the light photons striking at that point. Each pixel store a value proportional to the light intensity at that particular...

Part 6: IELTS Academic Writing Task 1 For Diagram/Graph Vocabulary

Vocabulary to show the sequence: You must write a summary of at least 150 words in response to a specific graph (bar, line, or pie graph), table, chart, or procedure in Writing Task 1 of the IELTS Academic test (how something works, how something is done). This job assesses your ability to choose and report the most important aspects, describe and compare data,...

Part 5: IELTS Academic Writing Task 1 Formal and Informal expressions.

Formal and Informal expressions and words: You must write a summary of at least 150 words in response to a specific graph (bar, line, or pie graph), table, chart, or procedure on the IELTS Academic test (how something works, how something is done). Few more informal expressions with their formal versions are given below. Since IELTS is a formal test, your writing...