Am I done with this Linked List code?

Question

Hi I'm trying to get some practice with Linked Lists.

I Defined an Object class called Student:

public class Student
{
      protected string  Student_Name;
      protected int Student_ID;
      protected int Student_Mark;
      protected char    Student_Grade;

      public Student()  // default Constructor
      {
         Student_Name = "           ";
         Student_ID = 0;
         Student_Mark = 0;
         Student_Grade = ' ';
        }

      public Student(string Sname, int Sid, int Smark, char Sgrade) // Constructor
      {
         int len = sname.Length;
         Student_Name = sname.Substring(0, len);
         //Student_Name = sname.Substring(0, sname.Length);
         Student_ID = Sid;
         Student_Mark = Smark;
         Student_Grade = Sgrade;
      }
}

and then a Node class:

public class S_Node
{
      public Student    Element;
      public S_Node Link;

      public S_Node()
      {
         Element = new Student();
         Link = null;
      }

      public Node(Student theElement)
      {
         Element = theElement;
         Link = null;
      }
}

and the LinkedList:

public class S_LinkedList
{
    protected S_Node header;
    protected S_Node tail;

    public S_LinkedList()
    {
       header = new S_Node();
       Tail = new S_Node();
       header.Link = Tail;
    }

    // METHODS which i don't know how to do it (never use linkedlist before)
}

I need to organize this data using a “linkedlist data structure type”.

Contain all methods of linkedlist as Adding nodes to the list as I've learned -->(Insert),Deleting nodes from the list,as I've learned -->((Remove),Traversing the lists I've learned -->((PrintList),Finding a node in the list as I've learned -->((Find , FindPrevious) the problem I'm selflearning and I've tried to search the net and read more from the stupid C# that was a disaster. I've done too much that I'm so sad that i don't know how to complete it .

I'm trying hard to Use this classes to write an executable program and to Test it .

If you don't want to help in completing this program (hope not) at least show me some real examples or ideas , after all I'm a selflearner geek :-)

Answer 1

 the head of the list.
 ( item1
   Element: student1
   Next ------------> ( item2
  )                     Element: student2
                        Next ------------> ( item3
                      )                      Element: student3
                                             Next: null
                                           )
                                           the tail of the list.

First of all, for you to be able to write the StudentList class, you need to write the client code first. Client code is the code that uses your student list. Also, don't just write one thing at a time and throw it away. Instead write a whole bunch of [test] cases that exercise the different ways you need to interact with the StudentList. Write exceptional cases too. But don't be tempted to write a swiss-army knife of a class that does everything just because it can. Write the minimal amount of code that gets the job done.

How you need to use the class will heavily dictate how the class is constructed. This is the essence of TDD or Test Driven Design.

Your biggest problem that I can see is you have no idea how you want to use the class. So lets do that first.

// create a list of students and print them back out.
StudentList list = new StudentList();
list.Add( new Student("Bob", 1234, 2, 'A') );
list.Add( new Student("Mary", 2345, 4, 'C') );

foreach( Student student in list)
{
    Console.WriteLine(student.Name);
}

I add the students to the list, and then I print them out.

I have no need for my client code to see inside the StudentList. Therefore StudentList hides how it implements the linked list. Let's write the basics of the StudentList.

public class StudentList 
{
    private ListNode _firstElement; // always need to keep track of the head.

    private class ListNode
    {
        public Student Element { get; set; }
        public ListNode Next { get; set; }
    }

    public void Add(Student student) { /* TODO */ }

}

StudentList is pretty basic. Internally it keeps track of the first or head nodes. Keeping track of the first node is obviously always required.

You also might wonder why ListNode is declared inside of StudentList. What happens is the ListNode class is only accessible to the StudentList class. This is done because StudentList doesn't want to give out the details to it's internal implementation because it is controlling all access to the list. StudentList never reveals how the list is implemented. Implementation hiding is an important OO concept.

If we did allow client code to directly manipulate the list, there'd be no point having StudentList is the first place.

Let's go ahead and implement the Add() operation.

public void Add(Student student)
{
    if (student == null)
        throw new ArgumentNullException("student");

    // create the new element
    ListNode insert = new ListNode() { Element = student };

    if( _firstElement == null )
    {
        _firstElement = insert;
        return;
    }

    ListNode current = _firstElement;
    while (current.Next != null)
    {
        current = current.Next;
    }

    current.Next = insert;
}

The Add operation has to find the last item in the list and then puts the new ListNode at the end. Not terribly efficient though. It's currently O(N) and Adding will get slower as the list gets longer.

Lets optimize this a little for inserts and rewrite the Add method. To make Add faster all we need to do is have StudentList keep track of the last element in the list.

private ListNode _lastElement;  // keep track of the last element: Adding is O(1) instead of O(n)

public void Add(Student student)
{
    if( student == null )
        throw new ArgumentNullException("student");

    // create the new element
    ListNode insert = new ListNode() { Element = student };

    if (_firstElement == null)
    {
        _firstElement = insert;
        _lastElement = insert;
        return;
    }

    // fix up Next reference
    ListNode last = _lastElement;
    last.Next = insert;
    _lastElement = insert;
}

Now, when we add, we don't iterate. We just need to keep track of the head and tail references.

Next up: the foreach loop. StudentList is a collection, and being a collection we want to enumerate over it and use C#'s foreach. The C# compiler can't iterate magically. In order to use the foreach loop We need to provide the compiler with an enumerator to use even if the code we write doesn't explicitly appear to use the enumerator.

First though, lets re-visit how we iterate over a linked list.

// don't add this to StudentList
void IterateOverList( ListNode current )
{
    while (current != null)
    {
        current = current.Next;
    }
}

Okay. so let's hook into C#'s foreach loop and return an enumerator. To do that we alter StudentList to implement IEnumerable. This is getting a little bit advanced, but you should be able to figure out what's going on.

// StudentList now implements IEnumerable<Student>
public class StudentList : IEnumerable<Student>
{
    // previous code omitted

    #region IEnumerable<Student> Members
    public IEnumerator<Student> GetEnumerator()
    {
        ListNode current = _firstElement;

        while (current != null)
        {
            yield return current.Element;
            current = current.Next;
        }
    }
    #endregion

    #region IEnumerable Members
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    #endregion
}

You should be able to spot the linked list iteration in there. Don't get thrown by the yield keyword. All yield is doing is returning the current student back to the foreach loop. The enumarator stops returning students when it gets to the end of the linked list.

And that's it! The code works the way we want it to.

---

* This is by no means the only way to implement the list. I've opted to put the list logic in the StudentList and keep ListNode very basic. But the code does only what my very first unit test needs and nothing more. There are more optimizations you could make, and there are other ways of constructing the list.

Going forward: What you need to do is first create [unit] tests for what your code needs to do, then add the implementation you require.

---

* fyi I also rewrote the Student class. Bad naming and strange casing from a C# persepctive, not to mention the code you provided doesn't compile. I prefer the _ as a leader to private member variables. Some people don't like that, however you're new to this so I'll leave them in because they're easy to spot.

public class Student
{
    private string _name;
    private int _id;
    private int _mark;
    private char _letterGrade;

    private Student()  // hide default Constructor
    { }

    public Student(string name, int id, int mark, char letterGrade) // Constructor
    {
        if( string.IsNullOrEmpty(name) )
            throw new ArgumentNullException("name");
        if( id <= 0 )
            throw new ArgumentOutOfRangeException("id");

        _name = name;
        _id = id;
        _mark = mark;
        _letterGrade = letterGrade;
    }
    // read-only properties - compressed to 1 line for SO answer.
    public string Name { get { return _name; } }
    public int Id { get { return _id; } }
    public int Mark { get { return _mark; } }
    public char LetterGrade { get { return _letterGrade; } }
}

• check parameters
• pay attention to the different casing of properties, classes, and variables.
• hide the default constructor. Why do I want to create students without real data?
• provide some read-only properties.
  • This class is immutable as written (i.e. once you create a student, you can't change it).