Stack Simulation with Double Linked List

Question

I'm trying to create a program that simulates a stack. The requirements are:

a structure called node
an integer named data
two pointers of the same type node named next and previous
void push(int) prototype int pop() prototype

I have built my push() function like so:

#include <stdio.h>

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

struct node *first = NULL;
void push(int number);
int pop();

int main() {
int choice = 0, number;

printf("Enter your choice: \n"
    "1) Push integer\n"
    "2) Pop integer\n"
    "3) Exit\n");
scanf("%d", &choice);

while (choice != 3) {
    if (choice == 1) {
        printf("Enter Integer: ");
        scanf("%d", &number);
        printf("\n");
        push(number);
    }
    if (choice == 2) {
        number = pop();
        if (number == -1) {
            printf("Error: Stack empty.\n\n");
        }
        else {
            printf("Integer %d is popped.\n\n", number);
        }
    }

    printf("Enter your choice: \n"
        "1) Push integer\n"
        "2) Pop integer\n"
        "3) Exit\n");
    scanf("%d", &choice);
}
}


void push(int number)
{
 struct node *cur;
 cur = first;

 if (cur == NULL) {
     cur = (struct node *) malloc(sizeof(struct node));
     cur->data = number;
     cur->next = NULL;
     cur->prev = cur;
     first = cur;
     return;
 }

 if (cur != NULL) {
     while (cur->next != NULL) {
         cur = cur->next;
     }
     (cur->next) = (struct node *) malloc(sizeof(struct node));
     (cur->next)->data = number;
     (cur->next)->next = NULL;
     (cur->next)->prev = cur;
 }
}    

int pop() {
int number;

if (first == NULL) {
    return -1;
}
else {
    struct node *cur, *prev;
    cur = first;
    prev = NULL;

    while (cur->next != NULL) {
        prev = cur;
        cur = cur->next;
    }

    number = cur->data;

    if (prev == NULL) {
        first = NULL;
    }
    else {
        prev->next = cur->next;
    }

    return number;
}
}

Does this look okay? My main program freezes up after the user enters a number to push.

As a side note, your if (cur != NULL) is redundant with the while (cur != NULL) it contains, as your program won't enter the loop if the condition is not initially true anyways. — zneak
– zneak, Commented Sep 1, 2011 at 1:52
Thanks for catching that! I've changed I got rid of the if statement altogether. — raphnguyen
– raphnguyen, Commented Sep 1, 2011 at 2:01
@raphnuguyen what happens if first is NULL(when you are pushing the first node) — Muthu Ganapathy Nathan
– Muthu Ganapathy Nathan, Commented Sep 1, 2011 at 3:13
@EAGER_STUDENT thanks so much for all of your help! I was able to complete the rest of it and the pop() method as well. — raphnguyen
– raphnguyen, Commented Sep 1, 2011 at 3:36

Muthu Ganapathy Nathan · Accepted Answer · 2011-09-01 03:19:23Z

2

Do like this...This is meet your requirements...

 void push(int number)
 {
    struct node *cur;
    cur = first;
    if(cur == NULL)  //if it is first node
     {
    cur = (struct node*) malloc(sizeof(struct node));
    cur->data = number;
    cur->next = NULL;
    cur->prev = cur;
    first = cur;
    return;
     }

    //note here Iam running the loop till cur->next!=NULL and not till cur != NULL. cur!=NULL makes the cur to act as head of a yet another new Linked List.

    while (cur->next != NULL)
    cur = cur->next;

    (cur->next) = (struct node*) malloc(sizeof(struct node));
    (cur->next)->data = number;
    (cur->next)->next = NULL;
    (cur->next)->prev = cur;
}

Or you want to make your implementation.... Then...

void push(int number)
{
 struct node *cur;
 cur = first;

 if (cur != NULL) {
     while (cur->next != NULL) {
         cur = cur->next;
     }
     (cur->next) = (struct node *) malloc(sizeof(struct node));
     (cur->next)->data = number;
     (cur->next)->next = NULL;
     (cur->next)->prev = cur;
 }
 else {/*Take action if it is a first node (if cur is NULL)*/}
}

Facts on your old code..

void push(int number) {
struct node *cur;
cur = first;

if (cur != NULL) {
    cur->prev = NULL;//no need. cur->prev must be NULL,already. since cur points to first.
                     //dont change cur->prev=someAddress it will change your head node
}


while (cur != NULL) {//flaw: run till cur->next!= NULL.Dont make cur NULL.
        cur->prev = cur; //during iteration to last element no need of prev.
        cur = cur->next;
    }

//Do memory allocation,for cur->next and not for cur after this loop

cur->data = number; // change this to cur->next->data = number.
//initialize cur->next->prev,cur->next->next


if (cur->prev == NULL) {
    first = cur;
}
//I can get your idea. But if you want to do this way,
//you have to use additional pointer like temp.

else {
    cur->prev->next = cur;
}

}

edited Sep 1, 2011 at 3:19

answered Sep 1, 2011 at 2:38

Muthu Ganapathy Nathan

3,32717 gold badges50 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

raphnguyen Over a year ago

Something weird is going on. I left out the if (cur == NULL) statement. My code is revised on the original post. This code runs even though first is NULL and it should never enter into the if statement. I have included my main method as well to see where the issue lies.

Mona Jalal Over a year ago

if we use a doubly linked list for stack simulation, does it mean that reversing the stack will happen in constant time?

Kat · Accepted Answer · 2011-09-01 02:27:51Z

2

You should probably check if cur is NULL before you dereference it in the line

cur->prev = NULL;

Also I think somewhere in your push function you should make a new node. To actually make a new node you need to do something like:

struct node * cur = malloc(sizeof(struct node));
cur->data = number;
cur->prev = NULL;
cur->next = first;
first = cur;

This will actually create space on the heap for you to put your new node. Note I pushed onto the beginning of the stack, so you don't have to search through the whole thing. The malloc line will be the same regardless.

edited Sep 1, 2011 at 2:27

answered Sep 1, 2011 at 1:56

Kat

1,66417 silver badges24 bronze badges

4 Comments

raphnguyen Over a year ago

Thanks! I wrapped that statement in an if (cur != NULL). Is a new node not being created at the end of my push()?

Kat Over a year ago

What lines are you referring to? I don't see you actually allocating memory for your new node with new in c++ or malloc in c.

raphnguyen Over a year ago

Looks like this is where my confusion is. Can you give me an example as to what syntax I would use in my code to create a new node? I'm programming in C.

Kat Over a year ago

I have added it to my answer.

Mu Qiao · Accepted Answer · 2011-09-01 01:54:43Z

1

You'd better save the head of the linked list, then your push_front/pop_front operation would be much simpler.

answered Sep 1, 2011 at 1:54

Mu Qiao

7,1271 gold badge34 silver badges35 bronze badges

2 Comments

raphnguyen Over a year ago

Doesn't a stack push to the back and pop from the back? Will I still benefit from creating a new node if a stack operates this way?

Mu Qiao Over a year ago

You always have to create a new node if you're pushing. Either at back or at front is up to you, just make sure you have a correct stack representation.

amalloy · Accepted Answer · 2011-09-01 02:43:36Z

You only need a singly-linked list, and you need to allocate memory for it. struct node *node; only allocates space for a pointer to a node, not for an actual node. Here's a full application that does some basic stack manipulation:

#include <stdio.h>
#include <stdlib.h>

struct node {
  struct node *next;
  int data;
};

struct node *push(struct node *head, int num) {
  struct node *newNode = malloc(sizeof(*head));
  newNode->next = head;
  newNode->data = num;
  return newNode;
}

int pop(struct node **headPtr) {
  struct node *top = *headPtr;
  int data = top->data;
  *headPtr = top->next;
  free(top);
  return data;
}


int main(int argc, char **argv) {
  struct node *head = NULL;
  int i;
  for (i = 1; i < argc; i++) {
    head = push(head, atoi(argv[i]));
  }

  while (head) {
    int x = pop(&head);
    printf("%d ", x);
  }

  return 0;
}

$ make tmp
cc     tmp.c   -o tmp

$ ./tmp 1 4 9
9 4 1

Mayank Awasthi · Accepted Answer · 2020-08-24 21:13:06Z

#In Python 
class Node():
    """Defining a Node for Doubly linked List"""
    def __init__(self,value):
        self.value=value
        self.prev_node=None
        self.next_node=None

class DoubleLinkedList():
    """ A class and object Pointing to Doubly linked List"""
    def __init__(self):
        self.head=None
    #Adding Element in Doubly linked List in the tail of head   
    def add_element(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            return
        crnt_node=self.head
        while crnt_node.next_node is not None:
            crnt_node=crnt_node.next_node
        node.prev_node=crnt_node
        crnt_node.next_node=node
    #Adding a New Head in Doubly linked List
    def add_head_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            return
        crnt_node=self.head
        while crnt_node.next_node is not None:
            break
        crnt_node.prev_node=node
        vnode=crnt_node
        node.next_node=vnode
        crnt_node=node
        self.head=crnt_node
    #Adding a New tail in Doubly linked List
    def add_tail_node(self,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            return
        crnt_node=self.head
        while True:
            if crnt_node.next_node is None:
                break
            crnt_node=crnt_node.next_node
        node.prev_node=crnt_node
        crnt_node.next_node=node
    #Adding a New node in between in Doubly linked List
    def add_bw_node(self,aftr_node_value,value):
        node=Node(value)
        if self.head is None:
            self.head=node
            return
        crnt_node=self.head
        while True:
            if crnt_node.value==aftr_node_value:
                half_node=crnt_node.next_node
                break
            crnt_node=crnt_node.next_node
        node.prev_node=crnt_node
        half_node.prev_node=node
        node.next_node=half_node
        crnt_node.next_node=node
    #Deleting a Head node in Doubly linked List
    def del_head_node(self):
        if self.head is None:
            print('Empty Double Linked List')
            return
        crnt_node=self.head
        while True:
            if crnt_node.next_node is not None:
                half_node=crnt_node.next_node
                break
            crnt_node=crnt_node.next_node
        #crnt_node.prev_node=None
        crnt_node.next_node=half_node
        half_node.prev_node=None
        self.head=crnt_node.next_node
    #Deleting a tail node in Doubly linked List
    def del_tail_node(self):
        if self.head is None:
            print('Empty Double Linked List')
            return
        crnt_node=self.head
        while True:
            if crnt_node.next_node.next_node is None:
                crnt_node.next_node=None
                break
            crnt_node=crnt_node.next_node
    #Deleting a in between node in Doubly linked List
    def del_inbw_node(self,inbw_node_value):
        if self.head is None:
            print('Empty Double Linked List')
            return
        crnt_node=self.head
        while True:
            if crnt_node.next_node.value==inbw_node_value:
                half_node=crnt_node.next_node.next_node
                break
            crnt_node=crnt_node.next_node
        half_node.prev_node=crnt_node
        crnt_node.next_node=half_node
    #Traversing node to node in Doubly linked List
    def print_dllist(self):
        crnt_node=self.head
        while True:
            print(crnt_node.value,end='->')
            if crnt_node.next_node is None:
                break
            crnt_node=crnt_node.next_node
        print('None')
    #Traversing previous nodes in Doubly linked List
    def print_previous_node(self):
        crnt_node=self.head
        while crnt_node.next_node is not None:
            if crnt_node.prev_node is None:
                print(f'{crnt_node.prev_node}<-',end='')
            else:
                print(f'{crnt_node.prev_node.value}<-',end='')
            crnt_node=crnt_node.next_node
        print(crnt_node.prev_node.value)

dllist=DoubleLinkedList()
dllist.add_element(10)
dllist.print_dllist()
dllist.add_element(20)
dllist.print_dllist()
dllist.add_element(30)
dllist.print_dllist()
dllist.add_element(40)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_head_node(5)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_tail_node(50)
dllist.print_dllist()
#dllist.print_previous_node()
dllist.add_bw_node(40,45)
dllist.print_dllist()
dllist.del_head_node()
dllist.print_dllist()
#dllist.print_previous_node()
dllist.del_tail_node()
dllist.print_dllist()
#dllist.print_previous_node()
dllist.del_inbw_node(30)
dllist.print_dllist()
dllist.print_previous_node()

Collectives™ on Stack Overflow

Stack Simulation with Double Linked List

5 Answers 5

2 Comments

4 Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

4 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related