I want to change some pointers around in a linked list, and I was wondering if I could use the STL list for the purpose.
I want to do something like this:
Is it possible with stl?
2 Likes
There’s no stl method for rotating a linked list, however you can do this with a std:vector.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> l;
vector<int> :: iterator it;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
rotate(l.begin(), l.begin()+2, l.end()); //stl rotation
for(it=l.begin(); it!=l.end(); it++) {
cout << *it << " ";
}
return 0;
}
Please correct me if I am wrong.
1 Like
The rotate method, as far as I can tell, should be O(n) and will beat the purpose of using a linked list for the task.
The only way to achieve this in O(1) time is to use a custom linked list then?
I think a custom linked list can not complete this task in constant O(1) time. In worst case you have to perform n operations/swaps. Take a look at this link and share you views. Meanwhile let me try this with custom linked list.
I think it can, you only have to delete one pointer (2->3), and add one pointer(5->1). But then I suppose finding those pointers will take linear time, so you can only do it in constant time if you already have a reference to those particular pointers. Finding and creating (5->1) should be O(1), but searching for (2->3) will indeed be O(n)
1 Like
That was a typo…
You can reach at the pointer in constant time using
advance(it, distance) if you use random-access iterators.
Time complexity is constant for random-access iterators.
swap_ranges, copy, copy_n, fill_n every function takes O(n) time.
1 Like
Thing is, linked lists are not random access. So it’d take O(n) to find the pointer.
1 Like
off course 
:thumsup
1 Like
~Thanks for the help!
//l is initial list here list. I first copy those values in a temporary list then and erase them from initial list. Then I inserted //them in front from l.begin() that is in front.
list <int> temp(find(l.begin(), l.end(), 3), l.end());
l.erase(find(l.begin(), l.end(), 3), l.end());
l.insert(l.begin(), temp.begin(), temp.end());
Of course it’s possible in O(n) time, I wanted to ask whether the operations were possible in O(1) time.
If you already have the iterator to the position in the middle where you want to make the cut, you can do this in O(1) in an C++ STL list using splice.
1 Like
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct sllist
{
int data;
struct sllist *next;
};
struct sllist head=NULL;
void insert(int data,int position);
void Delete(int position);
void display(void);
void change(void);
int main()
{
int p,ps;
char con;
printf(“Enter a Number:”);
scanf("%d",&p);
head=(struct sllist)malloc(sizeof(struct sllist));
head->data=p;
head->next=NULL;
do
{
printf("\nFOR INSERTION PRESS i");
printf("\nFOR DISPLAY PRESS d");
printf("\nFOR EXIT PRESS e");
printf("\nFOR YOUR CHOICE:");
con=getche();
printf("\n");
switch(con)
{
case ‘i’:
{
printf(“ENTER DATA:”);
scanf("%d",&p);
printf(“ENTER POSITION:”);
scanf("%d",&ps);
insert(p,ps);
break;
}
case ‘d’:
{
display();
break;
}
}
}while(con!=‘e’);
change();
display();
}
void insert(int data,int position)
{
struct sllist temp,node;
if(position==1)
{
temp=(struct sllist)malloc(sizeof(struct sllist));
temp->data=data;
temp->next=head;
head=temp;
return;
}
else
{
temp=head;
int i=2;
while((temp->next!=NULL)&&(i++<position))
temp=temp->next;
if(i<position)
{
printf("\nGIVEN POSITION DOES NOT EXIST");
return;
}
node=(struct sllist)malloc(sizeof(struct sllist));
node->data=data;
node->next=temp->next;
temp->next=node;
}
}
void display(void)
{
struct sllist *temp=head;
while(temp!=NULL)
{
printf("%d\t",temp->data);
temp=temp->next;
}
}
void change(void)
{
struct sllist *temp=head,*temp1=head->next;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
head=temp1->next;
temp1->next=NULL;
}
Blockquote