[go: up one dir, main page]
Scribd
Upload
36 views24 pages

Linked List: by Muhammad Tasaddaq Latif

This document discusses linked lists. Linked lists store elements non-contiguously in memory by linking each element (stored in nodes) to the next. Each node contains a data field for the element and a pointer field for the address of the next node. A head pointer is needed to access the first node. Nodes are linked together by placing the address of the next node in the pointer field. This allows dynamic memory allocation for variable sized lists. Operations like adding and removing nodes take constant time, while finding requires linear time in the worst case. C++ code demonstrates creating and traversing a linked list.

Uploaded by

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

Linked List: by Muhammad Tasaddaq Latif

This document discusses linked lists. Linked lists store elements non-contiguously in memory by linking each element (stored in nodes) to the next. Each node contains a data field for the element and a pointer field for the address of the next node. A head pointer is needed to access the first node. Nodes are linked together by placing the address of the next node in the pointer field. This allows dynamic memory allocation for variable sized lists. Operations like adding and removing nodes take constant time, while finding requires linear time in the worst case. C++ code demonstrates creating and traversing a linked list.

Uploaded by

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

Linked List

By
Muhammad Tasaddaq Latif

List Using Linked Memory

Various cells of memory are not allocated


consecutively in memory.
Not enough to store the elements of the list.
With arrays, the second element was right next
to the first element.
Now the first element must explicitly tell us
where to look for the second element.
Do this by holding the memory address of the
second element

Linked List

Create a structure called a Node.


object

next

The object field will hold the actual list element.


The next field in the structure will hold the
starting location of the next node.
Chain the nodes together to form a linked list.

Linked List

Picture of our list (2, 6, 7, 8, 1) stored as a


linked list:
head
2

6
current

size=5

Linked List
Note some features of the list:
Need a head to point to the first node of the list.
Otherwise we wont know where the start of the
list is.

Linked List
Note some features of the list:
Need a head to point to the first node of the list.
Otherwise we wont know where the start of the
list is.
The current here is a pointer, not an index.

Linked List
Note some features of the list:
Need a head to point to the first node of the list.
Otherwise we wont know where the start of the
list is.
The current here is a pointer, not an index.

The next field in the last node points to nothing.


We will place the memory address NULL which
is guaranteed to be inaccessible.

Linked List

Actual picture in memory:


current

head
2

1051

1052

1063

1053

1063

1054

1055

1051

1056

current

1057

1058

1060

1059

head

1060

1061

1062

1054

1063

1064

1057

1065

Linked List

Actual picture in memory:


current

head
2

1051

1052

1063

1053

1063

1054

1055

1051

1056

current

1057

1058

1060

1059

head

1060

1061

1062

1054

1063

1064

1057

1065

Building a Linked List


List list;

headNode

size=0

Building a Linked List


List list;

headNode

size=0
currentNode

list.add(2);

headNode
lastcurrentNode

size=1

Building a Linked List


List list;

headNode

size=0
currentNode

list.add(2);

headNode

size=1

lastcurrentNode
currentNode

list.add(6);

headNode

lastcurrentNode

size=2

Building a Linked List


List.add(8); list.add(7); list.add(1);
currentNode
headNode

lastcurrentNode

size=5

Traversing
(Traversing a Linked List) Let List be a linked list in
memory. This algorithm traverses List, applying an
operation process on each element of List. The variable
PTR points to the node currently being processed.

1- Set PTR=START[initializes pointer PTR]


2- Repeat Step 3 and 4 while PTR!=NULL
3- Apply Process to INFO[PTR]
4- Set PTR=Link[PTR] [PTR points next node]
[End of Step 2 Loop].
5- Exit.

C++ Code for Linked List


struct list
{

int data;
list* next;

}*f,*c,*p,*temp;
int t=0; //counter
void insert(void);
void print();

C++ Code for Linked List


int main()
{
system(cls);
insert();
print();
return 0;
}

C++ Code for Linked List


void insert(void)
{
int ch=1;
while(ch==1)
{
c=new list();
if(t==0) {
f=c;
p=c;
cout<<"enter value";
cin>>c->data;
c->next=NULL;
}//if

else {
p->next=c;
p=c;
cout<<"\n enter value";
cin>>c->data;
}//else
cout<<"\n press 1 to enter
another node ";
cin>>ch;
t++;
} //end of while
//if(ch!=1)
c->next=NULL;
temp=f;
} // end of insert

void print(void)
{
cout<<"\n value of link list
while(temp->next!=NULL)
cout<<temp->data<<" ";
temp=temp->next;
} end of while
cout<<temp->data<<" ";
}

";
{

C++ Code for Linked List


int get() {
if (currentNode != NULL)
return currentNode->get();
};

C++ Code for Linked List


bool next() {
if (currentNode == NULL) return false;
lastCurrentNode = currentNode;
currentNode = currentNode->getNext();
if (currentNode == NULL || size == 0)
return false;
else
return true;
};

Analysis of Linked List

add

we simply insert the new node after the current


node. So add is a one-step operation.

Analysis of Linked List

add

we simply insert the new node after the current


node. So add is a one-step operation.

remove

remove is also a one-step operation

Analysis of Linked List

add

remove

we simply insert the new node after the current


node. So add is a one-step operation.
remove is also a one-step operation

find

worst-case: may have to search the entire list

Analysis of Linked List

add

remove

we simply insert the new node after the current


node. So add is a one-step operation.
remove is also a one-step operation

find

worst-case: may have to search the entire list


back
moving the current pointer back one node requires
traversing the list from the start until the node whose
next pointer points to current node.

You might also like