Scribd
Upload
4 views24 pages

Singly Linked List

The document discusses linked lists and their advantages over arrays, highlighting the difficulties of resizing and element manipulation in arrays. It explains the structure and operations of singly linked lists, including adding, removing, and displaying nodes, as well as implementing a destructor and copy constructor. The document also provides code snippets for various linked list operations such as insertion, deletion, and reversing the list.

Uploaded by

brosy812
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views24 pages

Singly Linked List

The document discusses linked lists and their advantages over arrays, highlighting the difficulties of resizing and element manipulation in arrays. It explains the structure and operations of singly linked lists, including adding, removing, and displaying nodes, as well as implementing a destructor and copy constructor. The document also provides code snippets for various linked list operations such as insertion, deletion, and reversing the list.

Uploaded by

brosy812
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 24

Linked List

Dr. Rajni Bala


Disadvantages of Array
• Arrays are nice and simple for storing things in
a certain order, but they have drawbacks.
• They are not very adaptable. For instance, we
have to fix the size n of an array in advance,
which makes resizing an array difficult.
• Insertions and deletions are difficult because
elements need to be shifted around to make
space for insertion or to fill empty positions
after deletion.
Linked list
• A linked list, in its simplest form, is a collection of
nodes that together form a linear ordering.
• As in the children’s game “Follow the Leader,” each
node stores a pointer, called next, to the next node
of the list.
Singly linked list
• The next pointer inside a node is a link or pointer to the next node
of the list. Moving from one node to another by following a next
reference is known as link hopping or pointer hopping.
• The first and last nodes of a linked list are called the head and tail
of the list, respectively. Thus, we can link-hop through the list,
starting at the head and ending at the tail.
• The tail is the node having a null next reference.
• The structure is called a singly linked list because each node stores
a single link.
• Like an array, a singly linked list maintains its elements in a certain
order, as determined by the chain of next links.
• Unlike an array, a singly linked list does not have a predetermined
fixed size. It can be resized by adding or removing nodes
Class to represent a node
Singly Linked List Class

StringLinkedList l1;
l1.addFront(“Abc”);
L1.removeFront();
StringNode n;
n.elem n.next
StringNode *head=NULL
Head =0
head = new StringNode()

Head
100 elem next

head->elem
head->next
Singly linked list
Destructor of linked list
Node *p=Null;
while(head!=NULL)
{
p=head;
head=head->next;
delete p;
}
Copy Constructor
• Head 1->2->3->4
• l2.head 1->2->3->4
LinkedList l2(l1); l2.head=l1.head;
LinkedList(const LinkedList &l1)
{
P=l1.head;
Head=null;
while(p!=null)
{ newnode = new IntNode;
newnode->elem=p->elem;
newnode->next=null;
if (head==NULL) { head=newnode;p1=head;}
else
{p1->next=newnode;
p1=p1->next;
}
p=p->next;
}
Adding the node at the front
Removing node from the front
Display the linked list
void IntLinkedList::display() int IntLinkedList::count()
{ {
if(head==NULL) cout<< "Empty list ";
int count=0;
else {
IntNode* pt=head; IntNode* ptr=head;
while(pt!=NULL) while(ptr!=NULL)
{ {
// Printing the current
count++;
cout<<pt->elem;
// moving to next element ptr=ptr->next;
pt=pt->next; }
} return count;
}
}
1->2->3->10
2->4->6->20
Add at last

void LinkedList::addLast(int x)
{ IntNode *p = new IntNode;
p->elem=x;
p->next=NULL;

IntNode *temp=head;
if (empty()) {head=p; return;}
while(temp->next!=NULL) temp=temp->next;
temp->next= p;

}
Insert at a position
1-> 2-> 5-> 10
3N

1-> 2-> 3-> 5-> 10


1-> 2-> 5-> 10
Insert at a position
• 1-> 2-> 5-> 10
• L1.insert(pos=3,value=6)
• 1->2->6->5->10
insert(int pos, int value)
{
Intnode *p = new Intnode;
p->elem=value;
ptr = head;
if (pos==1)
{
p->next=head;head=p;return;}
count=1;
while(ptr!=NULL && count<pos-1)
{ ptr=ptr->next;
count++;
}
if (ptr==NULL) throw “Invalid Position”;
p->next= ptr->next;
ptr->next = p;

}
Delete an element a given pos
• 1->2->6->5->10
• 1->2-> 5->10
• delete(pos=3)
delete(int pos)
{
ptr = head;
if (head==0) throw “Empty List. Deletion not possible”;
if (pos==1)
{
old=head;
head= old->next; delete old;;return;}
count=1;
while(ptr!=NULL && count<pos-1)
{ ptr=ptr->next;
count++;
}
if (ptr==NULL) throw “Invalid Position”;
intnode *old=ptr->next;
p-tr>next= old->next;
delete old;
Delete a given value
• 1->2->6->5->10
• delete(value=5)
delete(int value)
{
if (head==0) throw “Empty List. Deletion not possible”;
ptr = head;
prev =null;
while(ptr!=Null && ptr->elem!=value)
{
prev=ptr;
ptr=ptr->next;
}
if (ptr==NULL) throw “Invalid value”;
if (prev==null) head=head->next;
else prev->next= ptr->next;
delete ptr;

}
Class to represent linkedlist
Class LinkedList
{ IntNode *head,*tail;
public:
LinkedList(){ head=tail=0;}
void addFront(int x);
void addTail(int x);
void removeTail();
void removeHead();
void display();
int count();
void delete(int pos)
void delete(int value)
void insert(pos, value);
}
• LinkedList l1;
• L1.addFront(2) head -> 2
• tail
• L1.addFront(3) 3->2
addFront
l1
LinkedList l1;
Head Tail
NULL NULL

l1.addFront(5)

IntNode *newnode = new IntNode;


newnode 5 NULL Newnode->elem = x;
Newnode->next = NULL
If (head==NULL)
head = tail = newnode;
addFront cont.
l1
LinkedList l1;
Head Tail

l1.addFront(5)

IntNode *newnode = new IntNode;


newnode 5 NULL Newnode->elem = x;
Newnode->next = NULL
If (head==NULL)
head = tail = newnode;
addFront
head tail
l1.addFront(5)

5 NULL IntNode *newnode = new IntNode;


Newnode->elem = x;
Newnode->next = NULL
If (head==NULL)
10 NULL head = tail = newnode;
Else
newnode->next=head;
head=newnode;
Reversing a SLL
tail
head head
tail
5 6 7 8 9

p p p1 p p1 p p1 p p1 p1
if (empty()) return;
p=head;
p1 = head->next;
if (p1==NULL) return;
while(p1!=NULL){
p2=p1->next;
p1->next =p;
p = p1;
p1 = p2;
}
head->next=NULL;
tail = head;
head= p;
return;

You might also like