Skip to content

Instantly share code, notes, and snippets.

@szolotykh
Created May 8, 2013 00:05
Show Gist options
  • Save szolotykh/45a941b0c09bf63325a8 to your computer and use it in GitHub Desktop.
Save szolotykh/45a941b0c09bf63325a8 to your computer and use it in GitHub Desktop.
Linking list
class listNode{
public:
listNode *previous;
listNode *next;
int val;
bool remove(){
this->previous->next=this->next;
this->next->previous=this->previous;
delete this;
return true;
}
bool isFirst(){
return (this->previous->previous==NULL)?true:false;
}
bool isLast(){
return (this->next->next==NULL)?true:false;
}
};
class list{
listNode* firstHeader;
listNode* lastHeader;
public:
list(){
firstHeader = new listNode;
lastHeader = new listNode;
firstHeader->previous=NULL;
firstHeader->next=lastHeader;
lastHeader->previous=firstHeader;
lastHeader->next=NULL;
}
listNode* addNode(int val){
listNode* node = new listNode;
node->val=val;
node->previous=this->lastHeader->previous;
node->next=this->lastHeader;
this->lastHeader->previous->next=node;
this->lastHeader->previous=node;
return node;
}
bool isEmpty(){
return (this->firstHeader->next->next==NULL)?true:false;
}
listNode* getFirst(){
return (!this->isEmpty())?this->firstHeader->next:NULL;
}
listNode* getLast(){
return (!this->isEmpty())?this->lastHeader->previous:NULL;
}
int getSize(){
if(this->isEmpty())
return 0;
int i=0;
listNode* n=this->getFirst();
while(n){
i++;
if(n->isLast())
break;
n=n->next;
}
return i;
}
listNode* getByInd(int ind){
int size=this->getSize();
if(size==0||ind>=size)
return NULL;
listNode* n;
int i;
if(ind<size/2){
i=0;
n=this->getFirst();
while(true){
if(i==ind)
break;
n=n->next;
i++;
}
}
else{
i=size-1;
n=this->getLast();
while(true){
if(i==ind)
break;
n=n->previous;
i--;
}
}
return n;
}
};
int main(){
list* l1 = new list();
l1->addNode(1);
l1->addNode(2);
l1->addNode(3)->remove();
l1->addNode(4);
l1->addNode(5);
listNode* n=l1->getFirst();
while(n){
cout<<n->val<<endl;
if(n->isLast())
break;
else
n=n->next;
}
cout<<"Size = "<<l1->getSize()<<endl;
cout<<"node = "<<l1->getByInd(2)->val<<endl;
getch();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment