CODEWITHSUNDEEP
c#
yche
yche

Reputation: 3

Stack implementation that a class contains an object of the same class

I've read a code of Stack implementation in C#.

The code is working but I don't understand whether it is illegal (I am sure it is legal as I can compile it) to have a object of a class inside the same class. The code is as follows.

public class Stack{

    Entry top;

    public void Push(object data){
        top = new Entry(top, data);    
    }

    public object Pop(){
        if(top==null) throw new InvalidOperationException();    

        object result = top.data;   
        top = top.next;  

        return result;   
    }

    class Entry{

        public Entry next;//?
        public object data;

        public Entry(Entry next, object data){
            this.next = next;
            this.data = data;
        }

    }
}

The code is compiled and running ok.

I am confused that inside of the Entry class, it has a field next of Entry class.

Furthermore, when Stack is calling Push method, it calls the Entry constructor, which set this.next to next, but I don't understand how this works, this.next will point to object next, but where and how the object "next" being created.

I am very appreciated if someone could help me to understand the above code.

Upvotes: 0

Views: 65

Answers (2)

TimChang
TimChang

Reputation: 2417

Work flow like that

  1. Push() , top = new Entry(top, data); (A) , top.next <--- null

  2. Push() , top = new Entry(top, data); (B) , top.next <--- (A)

  3. Push() , top = new Entry(top, data); (C), top.next <--- (B)

  4. Pop() , return (C) , top = (B);

  5. Pop() , return (B) , top = (A);

  6. Pop() , return (A) , top = null ;

  7. Pop() , throw InvalidOperationException because top == null now.

    And your first question (where and how the object "next" being created)

First push is SPECIALY, it's next is null , But it's ok , because when pop() , It have null check.

Upvotes: 0

Sweeper
Sweeper

Reputation: 271990

The field next stores a reference to another object of Entry, or a null reference. Note that next could be null!

Your confusion probably comes from the misconception that to create an Entry, you must need an instance of Entry first, which seems quite circular on first sight. However, note that you could pass null as the first parameter:

Entry entry1 = new Entry(null, someObject);

Essentially, Entry represents a node in a linked list, which in turn is used to implement the stack:

A ---> B ---> C

The next of A is B. next of B is C. What's the next of C? It's null!

Upvotes: 3

Related Questions