DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
11 Monitoring and Observability Tools for 2023
Learn more
  1. DZone
  2. Data Engineering
  3. Data
  4. A Closer Look Into Linked List Data Structure

A Closer Look Into Linked List Data Structure

An overview on how linked list data is structured, and how this is expressed in code.

Marcus Biel user avatar by
Marcus Biel
·
Apr. 07, 17 · Opinion
Like (8)
Save
Tweet
Share
14.92K Views

Join the DZone community and get the full member experience.

Join For Free

This article is part of Marcus Biel’s free Java 8 course focusing on clean code principles. In this article, I will give a detailed explanation of the Linked List data structure. 

A pdf of the article is also available here.

Terminology

Let’s have a look at the term “LinkedList”. Why is LinkedList actually called LinkedList? For the term “Link” — as an analogy — think of a web link — when you click on it, it brings you from one website to the next. A list is a collection of related objects. Think of a shopping list — it contains every item that you plan to buy. So a LinkedList is a collection of related objects, where a link will bring you from one item to the next item.

Singly Linked List

Technically, in our LinkedList, an item or entry in the list is stored in a so-called “Node”. In our simple example, this entry is the number twenty-three. Each node has a link or pointer to the next element of the list, the next node. For every item that we want to add to the LinkedList, we create a node and store the item in it.LinkedList1The first item of the list is usually called the head, the last item of the list the tail of the list. For every new item, we create a new node and link to it from the last element of the list. So a LinkedList is a dynamic data structure that can hold any number of elements, as long as enough memory is available. After the list is created, to navigate through the list we call a function like next() which uses the link to go from one item to the next. This type of a LinkedList is called a Singly Linked List because the links only go in one direction — from the head of the list to the tail. So to navigate to the previous element, for example from the element 42 — to the element 9 — you have to go back to the head of the list – and you have to call the function next() — on every single element until you reach the element 9. If the list contains a lot of elements, this may take some time.

Inserting an element after the current element is relatively easy with a Singly Linked List. You create a new Node containing the new element. You link to the new element “17” from the current element “9”. You add a link pointing from the new “17” element to the existing “42” element. And you’re done. Inserting the same element before the current element is possible in a Singly LinkedList, but usually not very efficient. It will require navigating to the previous element, starting from the beginning of the list, as I showed you before. Removing an element from a Singly Linked List has the same issue – it is possible, but generally not very efficient.

LinkedList2

These operations get much easier, when you add a second link to each node, pointing to the previous element. This way you can navigate in both directions of the list. However, the extra link comes at a cost, of extra memory, as well as time to build the more complex structure. If this overhead is justified, I cannot generally answer, as it will differ for each use case. If performance is an issue, I advise you to test different options.

LinkedList3

Doubly Linked List

So a LinkedList that contains nodes that provide a link to the next and the previous node is called a “Doubly Linked List”. For every element that you add to a Doubly LinkedList, you need to create two links, so creating a Doubly Linked List is somewhat more complicated. Navigation in both directions in a Doubly Linked List is easier but at the cost of a more complex structure. Based on the two-way link structure adding or removing an element before or after the current element is relatively easy. Here we will add the element “17” before the current element “9”. The back link from element “9” to element “3” is removed and replaced by a back link to the new element “17”. From the new element “17” we link to the next element “9”. Next, we place a back link from 17 to 3. The old link from element 3 to 9 is replaced by a link from 3 to 17. Removing an element from a Doubly LinkedList has the same steps as inserting an element to the list, just in reverse order.

Image title

Let‘s look at a code excerpt of a Node in a Singly LinkedList below. So you have a method to retrieve the item of a Node and a method to go to the next Node. The Node of a Doubly LinkedList is very similar, but a bit more complex. Additionally, you have a reference to the previous Node. A LinkedList usually contains a link to the head of the List. The methods of the Node class will be used to navigate through the list. The concrete implementation of methods to get, add or remove an element from the list, depends on the type of the node, but such an implementation detail is usually hidden from a user of the list. Besides the direct link to the current node of the list and the head of the list, a LinkedList may also provide a direct link to the tail of the list. This is common for a Doubly Linked List, but may also be beneficial for a Singly Linked List.

Code Excerpts

public class Node<E> {
    private E item;
    private Node<E> previous;   
    private Node<E> next;   

public Node(E element, Node<E> previous, Node<E> next) {   
    this.item = element;       
    this.next = next;      
    this.previous = previous; 
}

public E item() {
    return item;
}

public Node<E> previous() {
    return previous;
}

public Node<E> next() {
    return next;
   }

 […]
}

public class LinkedList<E> {
    private Node<E> currentNode;
    private Node<E> head;

    public E get(int index) {…}
    public boolean add(E e) {…}
    public E remove(int index) {…}
  […]
}

Application scenarios

  • List
  • Queue
  • Stack
  • Double Ended Queue

Let’s have a look at different application scenarios for a LinkedList. A LinkedList can be used to implement data structures like List, Queue, Stack or Double Ended Queue. When comparing implementations based on a Singly- or a Doubly Linked List, there is no overall winner. Both have advantages and disadvantages that make them useful for different application scenarios. Using the example of List, Queue, Stack and Double Ended Queue we will in each case decide for a Singly- or a Doubly Linked based implementation. An implementation with other data structures, for example, an array, is also possible, but that’s a different story. A list usually requires random access to any element of the list, so I would recommend an implementation based on a Doubly Linked List. In a so-called “first in first out” Queue, new elements are inserted at the tail of the queue and removed from the head of the queue. Random access is not required, so I would recommend an implementation based on a Singly Linked List. A Stack provides a so-called “Last in First out” order. Elements are added and removed from the head of the Stack, which makes it even more simple than a Queue. Therefore a Singly Linked List is usually sufficient. A Double Ended Queue or Deque is a very dynamic data structure. It allows to access, add or remove elements from both ends. Therefore I would use a Doubly Linked List to implement a Deque.

Data structure Element Data (computing) Links

Published at DZone with permission of Marcus Biel, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • An End-to-End Guide to Vue.js Testing
  • Test Execution Tutorial: A Comprehensive Guide With Examples and Best Practices
  • Getting a Private SSL Certificate Free of Cost
  • Collaborative Development of New Features With Microservices

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: