Describe the features and characteristics of a dynamic data structure
Describe how linked lists operate logically.
Sketch linked lists (single, double and circular)
Linked List is a linear data structure, similar to arrays.
Linked list elements are not stored at contiguous location;
The elements are linked using pointers.
The size of the arrays is fixed. Upper limit on the number of elements has to be known in advance.
The allocated memory is equal to the upper limit irrespective of the usage generally.
Inserting a new element in an array of elements is expensive, as room has to be created for the new elements and to create room existing elements have to shifted.
Dynamic size
Ease of insertion/deletion
Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
Extra memory space for a pointer is required with each element of the list.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
class LinkedList
{
Node head; // head of list
/*Linked list Node*/
class Node
{
int data;
Node next;
/*Constructor to create a new node
Next is by default initialized
as null*/
Node(int d) {
data = d;
}
}
}
// A simple Java program to introduce a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
int data;
Node next;
//Constructor
Node(int d) {
data = d;
next = null;
}
}
/* method to create a simple linked list with 3 nodes */
public static void main(String[] args)
{
/*Start with the empty list
using the native LinkedList*/
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
/* Three nodes have been allocated dynamically.
We have references to these three blocks as first,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next = second; // Link first node with the second node
/* Now next of first Node refers to second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next = third; // Link second node with the third node
/* Now next of second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+ */
}
}
In Java, LinkedList class implements list interface. The class has the following methods:
boolean add(Object element) - appends the element to the end of the list
void add(int index, Object element) - inserts the element at the position "index" in the list
void addFirst(Object element) - inserts the element at the beginning of the list
void addLast(Object element) - appends the element at the end of the list
boolean contains(Object element) - returns true if the element is present in the list
Object get(int index) - returns the element at the position "index" in the list. It throws 'IndexOutOfBoundsException' if the index is out of range of the list.
int indexOf(Object element) - If element is found, it returns the index of the first occurrence of the element. Else, it returns - 1
Object remove(int index) - removes the element at the position 'index' in the list. It throws 'NoSuchElementException' if the list is empty.
int size() - returns the number of elements in the list
void clear() - removes all of the elements from the list
A node can be added in three ways
At the front of the linked list
After a given node.
At the end of the linked list.
The new node is always added before the head of the given Linked List.
And newly added node becomes the new head of the Linked List.
For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25.
Let us call the function that adds at the front of the list is add(). The add() must receive a pointer to the head pointer, because add must change the head pointer to point to the new node
Following are the four steps to add a node at the front of the LinkedList
/* This function is in LinkedList class. Inserts a
new Node at front of the list. This method is
defined inside LinkedList class shown above */
public void add(int new_data)
{
/* 1 & 2: Allocate the Node & Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
Time complexity of add() is O(1) as it does constant amount of work.
We are given pointer to a node, and the new node is inserted after the given node.
Following are the 5 steps to add node after a given node.
/* This function is in LinkedList class.
Inserts a new node after the given prev_node.
This method is defined inside LinkedList class shown above */
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}
/* 2. Allocate the Node & 3. Put in the data*/
Node new_node = new Node(new_data);
/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;
/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
Time complexity of insertAfter() is O(1) as it does constant amount of work.
The new node is always added after the last node of the given Linked List.
For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.
Following are the 6 steps to add node at the end.
/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then make the new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be the last node, so make next of it as null */
new_node.next = null;
/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
return;
}
Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimised to work in O(1) by keeping an extra pointer to tail of linked list/
Following is a complete program that uses all of the above methods to create a linked list.
// A complete working Java program to demonstrate all insertion methods
// on linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {
data = d;
next = null; }
}
/* Inserts a new Node at front of the list. */
public void add(int new_data)
{
/* 1 & 2: Allocate the Node & Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Inserts a new node after the given prev_node. */
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}
/* 2 & 3: Allocate the Node & Put in the data*/
Node new_node = new Node(new_data);
/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;
/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
/* Appends a new node at the end. This method is defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then make the new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be the last node, so make next of it as null */
new_node.next = null;
/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
return;
}
/* This function prints contents of linked list starting from the given node */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}
/* Driver program to test above functions. Ideally this function
should be in a separate user class. It is kept here to keep
code compact */
public static void main(String[] args)
{
/* Start with the empty list */
LinkedList llist = new LinkedList();
/*Insert 6. So linked list becomes 6->NUllist*/
llist.append(6);
/* Insert 7 at the beginning. So linked list becomes 7->6->NUllist */
llist.add(7);
/* Insert 1 at the beginning. So linked list becomes 1->7->6->NUllist */
llist.add(1);
/*Insert 4 at the end. So linked list becomes 1->7->6->4->NUllist */
llist.append(4);
/* Insert 8, after 7. So linked list becomes 1->7->8->6->4->NUllist */
llist.insertAfter(llist.head.next, 8);
System.out.println("\nCreated Linked list is: ");
llist.printList();
}
}
// This code is written by Rajat Mishra
Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
A singly linked list whose nodes contain two fields: an integer value and a link to the next node
In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case the list is said to be 'circular' or 'circularly linked'; otherwise it is said to be 'open' or 'linear'. It is a list where the last pointer points to the first node.
“Linked List Data Structure.” GeeksforGeeks, www.geeksforgeeks.org/data-structures/linked-list/.
LinkedList (Oracle Fusion Middleware Java API Reference for Oracle ADF Mobile Client), 2 Mar. 2011, docs.oracle.com/cd/E24001_01/apirefs.1111/e17503/oracle/adfnmc/java/util/LinkedList.html.
“Linked list.” Wikipedia, Wikimedia Foundation, 2 Feb. 2018, en.wikipedia.org/wiki/Linked_list.