a linked list is a data structure consisting of a group of nodes which together represent a sequence.
Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node
Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point(first node) into a linked list is called the Root or head or front of the list.
Two basic Types of Linked Lists 1. Singly Linked List 2. Doubly Linked List We can make as a Circular Linked List
Linked List Vs Array
In favor of Linked Lists.
The size of the arrays is fixed:
So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, upper limit is rarely reached. Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted. For example, suppose we maintain a sorted list of IDs in an array id[ ]. id[ ] = {1000, 1010, 1050, 2000, 2040, .....}. And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000). Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[ ], everything after 1010 has to be moved.
So Linked list provides following two advantages over
arrays 1) Dynamic size 2) Ease of insertion/deletion Linked lists have following drawbacks: 1) 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.
2) Extra memory space for a pointer is required with each element of the list. 3) Arrays have better performance.
Applications
Representing polynomials
In dynamic memory management
In symbol tables Representing sparse matrix
The cache in your browser that allows you to
hit BACK button. (linked list of URLs) UNDO functionality Stack, Queue,hash table, binary tree
Singly Linked List
Data structure consisting of sequence of
nodes. Each node consists of
Data
Link to next
And Link to next node
DATA INFO DATA DATA LINK LINK
Different naming conventions for a node
Data
node
ADDR Next
Our convention throughout the topic
DATA ADDR
10
NULL
First Node
Creating Nodes
20
NULL
Second Node
List after adding the second node(at end of first) 10 20 NULL 15 NULL
List after adding the third node(at end )
10
20
15
NULL
Common Operations of Singly Linked List
Creating a singly linked list Display the elements of a list Insert a node Insertion at Beginning Insertion in Middle Insertion at Last (Same logic of Creating a list) Delete a node Deletion of front/first node (Not much Priority is given to this) Deletion of last node (No much Priority is given to this) Deleting a particular node (Preferable for Implementation) Search for a element in the list
Declaration and Creation of a Node
Two ways of Node declarations: Use class or Use struct (Structure)
class Node { public: int data; Node *addr; } struct Node { int data; Node *addr; }
DATA ADDR
Let us follow class in declaring a node. In fact struct and class both are same with few differences. Try to find out the difference between struct and class.
class Node { public: int data; Node *addr; }*root;
root is the first node. Initially root = NULL Indicates List is empty
Again different naming conventions:
root node first node head node
Inserting a Node in Linked List
Display linked list
root
10
20
15 6 NULL
NULL
Insert a node at beginning of linked list root
10
20
15
NULL
root
Insert a node in middle of linked list
25
NULL
10 25
20
15
NULL
Class activities
Executing creation and display of singly linked list. Extending the program to perform
Inserting a node at beginning Extending the program to search for a node. Illustrating how deletion will be done. Implementing Linked stacks (Stacks using linked list). Topics covered in assignment: Deleting nodes Searching a node Inserting node in the middle of a linked list
