Singly linked vs doubly linked list
|
The main difference between Single Linked List and Double Linked List is that a node in the single linked list stores the address of the next node while a node in a double linked list stores the address of the next node and the previous node. Show An array is a data structure that stores a group of elements of the same data type. One major drawback of an array is that it is pre-defined or has a fixed length. A Linked List provides a solution to this issue as it allows storing data dynamically. Therefore, it is possible to add elements at runtime. In other words, a Linked List allows allocating memory for the elements when required. There are various types of linked lists, and single linked list and double linked list are two of them. In brief, a single linked list allows traversing to one direction while a double linked list allows traversing to both directions through the elements. Key Areas Covered1. What is Single Linked List Key TermsSingle Linked List, Double Linked List A linked list is a linear data structure that consists of a group of nodes in a sequence. A node or an element consists of data and the address of another node. A single linked list is a type of linked list. A single linked list stores the data and the address of the next node in the sequence. As the nodes stores the address of the next node, the nodes are referring to each other. Therefore, it forms a structure similar to a chain. It is possible to perform operations such as inserting, deleting and traversing through the elements in a single linked list. Similar to a single linked list, a double linked list is also a type of linked list. It is also called a doubly linked list. It stores data and two addresses. These addresses are the address of the next node and the address of the previous node. As there are two references, it is possible to go forward and backward through elements in the double linked list. Furthermore, the programmer can perform operations such as inserting elements and deleting elements in a double linked list. In addition to these two types, there is another linked list as a circular linked list. In this kind of list, the last node stores the address of the first node. Therefore, it forms a structure similar to a circular chain. DefinitionA single linked list is a linked list that contains nodes which have a data field and a next field which points to the next node in the line of nodes. A double linked list, in contrast, is a linked list that contains the data field, next field that points to the next node and a previous field that points to the previous node in the sequence. Thus, this is the main difference between Single Linked List and Double Linked List. DirectionMoreover, a single linked list allows traversing in one direction through the elements while a double linked list allows traversing in both directions (backward and forward). Memory RequirementMemory requirement is another difference between Single Linked List and Double Linked List. A single linked list requires less memory as it stores only one address while a double linked list requires more memory as it stores two address. Insertion and DeletionThe complexity of insertion and deletion at a known position in a single linked list is O(n). The complexity of insertion and deletion at a known position in a double linked list is O(1). Hence, this is another difference between Single Linked List and Double Linked List. ConclusionA linked list is a linear data structure that consists of a group of nodes in a sequence. It stores elements in noncontiguous memory locations at runtime. Single and double linked list are two types of linked lists. The main difference between Single Linked List and Double Linked List is that a node in the single linked list stores the address of the next node while a node in a double linked list stores the address of the next node and the previous node. Reference:1. “Introduction to Linked Lists.” Types of Network Topology in Computer Networks | Studytonight, Available here. Image Courtesy:1. “CPT-LinkedLists-addingnode” By Singly_linked_list_insert_after.png: Derrick Coetzeederivative work: Pluke (talk) – Singly_linked_list_insert_after.png (Public Domain) via Commons Wikimedia
This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy
Although this question has already been answered, I am somehow not satisfied with the answer (no offense meant), so here's how I would reply to it: What to use - Singly or Doubly linked list depends on what you intend to achieve and system limitations, if any. Singly-linked list: Pros: Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster. Cons: Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you’re deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time. --So, this should be used when you have lesser memory and your main goal is insertion/deletion and not searching elements. Doubly-linked list: Pros: Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous’ pointer. Cons: Relatively complex to implement, requires more memory for storage (1 ‘.previous’ pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous’ pointer for neighbor nodes) --This should be used when you have no or minimal limitations on memory, and your main goal is to search for elements. If there are some more pros and cons to any, please feel free to add, reply in comments. Thanks!
Java 8Object Oriented ProgrammingProgramming Both Singly linked list and Doubly linked list are the implementation of Linked list in which every element of singly-linked list contains some data and a link to the next element, which allows to keep the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node. The following are the important differences between a Singly linked list and Doubly linked list.
Example of Singly linked list vs Doubly linked listSinlgyLinkedList.java class Node { //create class Node public int data; public Node next; //create node parameter for pointer of next element public void displayNodeData() { System.out.println("{ " + data + " } "); } } public class SinglyLinkedList { private Node head; public boolean isEmpty() { return (head == null); } // used to insert a node at the start of linked list public void insertFirst(int data) { Node newNode = new Node(); newNode.data = data; newNode.next = head; head = newNode; } // used to delete node from start of linked list public Node deleteFirst() { Node temp = head; head = head.next; return temp; } // Use to delete node after particular node public void deleteAfter(Node after) { Node temp = head; while (temp.next != null && temp.data != after.data) { temp = temp.next; } if (temp.next != null) temp.next = temp.next.next; } // used to insert a node at the start of linked list public void insertLast(int data) { Node current = head; while (current.next != null) { current = current.next; // we'll loop until current.next is null } Node newNode = new Node(); newNode.data = data; current.next = newNode; } // For printing Linked List public void printLinkedList() { System.out.println("Printing LinkedList (head --> last) "); Node current = head; while (current != null) { current.displayNodeData(); current = current.next; } System.out.println(); } }ExampleLinkedListMain.java public class LinkedListMain { public static void main(String args[]){ SinglyLinkedList myLinkedlist = new SinglyLinkedList(); myLinkedlist.insertFirst(5); myLinkedlist.insertFirst(6); myLinkedlist.insertFirst(7); myLinkedlist.insertFirst(1); myLinkedlist.insertLast(2); Node node=new Node(); node.data=1; myLinkedlist.deleteAfter(node); myLinkedlist.printLinkedList(); } }OutputPrinting LinkedList (head --> last) { 1 } { 6 } { 5 } { 2 }ExampleDoublyLinkedListMain.java Live Demo public class DoublyLinkedList { class Node{ int data; Node previous; Node next; public Node(int data) { this.data = data; } } Node head, tail = null; public void addNode(int data) { //Create a new node Node newNode = new Node(data); if(head == null) { head = tail = newNode; head.previous = null; tail.next = null; } else { tail.next = newNode; newNode.previous = tail; tail = newNode; tail.next = null; } } public void display() { Node current = head; if(head == null) { System.out.println("List is empty"); return; } System.out.println("Nodes of doubly linked list: "); while(current != null) { System.out.print(current.data + " "); current = current.next; } } public static void main(String[] args) { DoublyLinkedList dList = new DoublyLinkedList(); dList.addNode(1); dList.addNode(2); dList.addNode(3); dList.addNode(4); dList.addNode(5); dList.display(); } }OutputNodes of doubly linked list: 1 2 3 4 5
 Published on 18-Sep-2019 13:29:45 |
