Linked list and doubly linked list in java

How to use LinkedList in Java? Singly LinkedList and Doubly LinkedList Example Tutorial

Hello friends, we meet again on our journey to Java. I hope you guys are enjoying Java and are trying hands-on too. Today we are gonna discuss a very easy topic (yeah, I mean it :p). But, do not get carried away just by «easy», this is the hottest topic asked in various interviews, exams, and development purposes too. So, what’s the wait? Let’s start! As usual, let’s start with a scenario. Let’s say you want a data structure that stores data in a sequential manner, like an array. But, you don’t know the size yet while initializing the data structure. Arrays don’t support that, they need a size beforehand. So, what should we do? Do not worry, as Java is here to help us again. Let’s explore it then!

What is Linked List Data Structure in Java?

LinkedList is a linear data structure similar to arrays in Java. LinkedList items, on the other hand, are not kept in contiguous places like arrays; instead, they are linked together via pointers. Each LinkedList member has a reference to the next LinkedList element.

The LinkedList class is provided by Java for the same use case. The items of the Java LinkedList class are stored as a double-linked list. It uses a linked-list data structure to store information. It implements the List and Deque interfaces and inherits the AbstractList class.

There are several types of Linked List that we can work on. And, we can customize and create our own LinkedList and modify it to any level we want. Let’s see two main types of linked list in Java

2. What is Singly Linked List in Java?

In programming, the linked list t is widely used. When we talk about a linked list, we’re talking about a single linked list. The singly-linked list is a data structure is divided into two parts: the data portion and the address part, which holds the address of the next or successor node.

A pointer is another name for the address portion of a node.

A single linked list contains only a single link. In this list, only forward traversal is possible; we cannot traverse in the backward direction as it has only one link in the list.

Representation:

class Node int data;
 Node next;
 Node(int data) this.data = data;
 this.next = null;
 >
>

In the illustration above, we’ve built a user-made class called Node, which has two fields: one is data of integer type, and the other is the node type’s pointer (next).

Java also provides a way to use LinkedList without creating a class ourselves. let us see a code example for the same.

2.1 Code Example:

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class MyLinkedList public static void main(String[] args) List list = new LinkedList<>();
 Scanner sc = new Scanner(System.in);
 for(int i=0;i5;i++) list.add(sc.nextInt());
 > 
 
list.forEach(System.out::println);
 >
>

3. Doubly linked list in Java

The doubly linked list, as its name implies, includes two pointers. The doubly linked list may be described as a three-part linear data structure: the data component, the address part, and the other two address parts. 

A doubly linked list, in other terms, is a list with three parts at each node: one data portion, a pointer to the previous node, and a pointer to the next node.

In a doubly-linked list, each node contains two address parts: one holds the address of the next node, while the other stores the address of the previous node. 

The address portion of the first node in the doubly linked list is NULL, indicating that the preceding node's address is NULL.

Representation:

class Node int data;
 Node prev;
 Node next;
 Node(int data) this.data = data;
 this.next = null;
 this.prev = null;
 >
>

In the model above, we’ve built a user-defined class called Node, which has three members: one is data of integer type, and the other two are pointers of the node type, i.e. next and prev. The address of the next node is stored in the next pointer variable, whereas the address of the previous node is stored in the prev pointer variable.

we have already seen how to use the LinkedList class instead of the List interface for this. let’s see how it is done.

import java.util.LinkedList;
import java.util.Scanner;

public class MyLinkedList public static void main(String[] args) LinkedList list = new LinkedList<>();
 Scanner sc = new Scanner(System.in);
 for(int i=0;i5;i++) list.add(sc.nextInt());
 > 
list.addFirst(0);
 list.addLast(10);

 list.removeFirst();
 list.removeLast();

 list.forEach(System.out::println);
 >
>

Hope you guys have understood basics of linked list. Hope to see you in the next article. But,

before that, let's see few real world applications of linked list. 

4. Applications:

Image viewer - Prior and next photos are connected, so the next and previous buttons may 
be used to access them.

Previous and next page in a web browser - Because they are linked as a linked list, we may
 
access previous and next urls searched in a web browser by hitting the back and next buttons
.
Music Player - The previous and next songs in the music player are connected. You can play
 
songs from the beginning or the end of the list.

See you in next article, till then, adios :D

Источник

Class LinkedList

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null ).

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be «wrapped» using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new LinkedList(. ));

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

Источник

Class LinkedList

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null ).

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be «wrapped» using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new LinkedList(. ));

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

Источник