Member Avatar for boiishuvo

How do you create a node with fullName and studentID in the "add" method and then put them into the correct positions which the name_first and name_second should move until the name in the name_first is larger than the new_Name and name_second is smaller than the new_Name?

public class NodeDemo{
        private String fullName;
        private int studentID;
        private NodeDemo fullNameLink;
        private NodeDemo studentIDLink;

        public NodeDemo(String newName, int newStudentID, NodeDemo newFullNameLink, NodeDemo newStudentIDLink){
            fullName = newName;
            studentID = newStudentID;
            fullNameLink = newFullNameLink;
            studentIDLink = newStudentIDLink;
        }

        private static NodeDemo startPosition;

        public void add(String new_Name, int newStudentID){
            NodeDemo name_First = startPosition.fullNameLink;
            NodeDemo name_Second = startPosition;
            NodeDemo studentId_First = startPosition.studentIDLink;
            NodeDemo studentId_Second = startPosition;

            NodeDemo node = new NodeDemo(new_Name, newStudentID, null, null);

        }
    }
  • 2 Contributors
  • 7 Replies
  • 299 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by JamesCherrill

Dani AI

Generated

A short, practical plan that ties together the thread: the data structure holds one Node per student but two separate next pointers (one ordering by name, one by ID). As pointed out, there are two valid strategies: insert into one list then repair the other, or find both insertion points first and then link a single new Node into both lists. The latter is safer and simpler to reason about because it avoids a transient state where the node exists in only one list.

The safe sequence (recommended):

  1. Traverse the name list to find the predecessor (prevName) and successor (curName) where the new name fits.
  2. Traverse the ID list to find predecessor (prevId) and successor (curId) where the new ID fits.
  3. Create one Node and perform four pointer updates: set the new node’s name-next to curName and prevName’s name-next to the new node; set the new node’s id-next to curId and prevId’s id-next to the new node. Handle head insertion by using a dummy/sentinel header or by special-casing updates to the list head.

A compact Java-style example (keeps a single new node and uses separate next fields):

/* assume: class Node { String name; int id; Node nextByName, nextById; }
   and a sentinel header with header.nextByName and header.nextById */
public void add(String name, int id) {
    Node prevN = header, curN = header.nextByName;
    while (curN != null && curN.name.compareToIgnoreCase(name) < 0) { prevN = curN; curN = curN.nextByName; }

    Node prevI = header, curI = header.nextById;
    while (curI != null && curI.id < id) { prevI = curI; curI = curI.nextById; }

    Node node = new Node(name, id);
    node.nextByName = curN; prevN.nextByName = node;
    node.nextById   = curI; prevI.nextById   = node;
}

Common pitfalls observed in the thread (relevant to ’s attempts): creating multiple Node objects for a single logical insert, using traversal variables as if they were heads, and dereferencing links before null checks. Using a sentinel header simplifies head cases and reduces special handling. For duplicate keys, decide a consistent tie-break rule (e.g., stable insert after equals).

Recommended Answers

All 7 Replies

Member Avatar for JamesCherrill

Is this a multiply-linked list? Do you know how to insert a node into a single-linked list?

Edited by JamesCherrill
Member Avatar for boiishuvo

Yeah. that would be

startPosition = new NodeDemo(newName, newStudentID, startPosition)

which enters a new node into the list.

Edited by boiishuvo
Member Avatar for JamesCherrill

That's what the method call could look like, but I meant do you know/understand the algorithm for inserting a node into the correct position in a singly-linked list? The multiply linked list can be confusing, but if you get the simpler single case working first then the multiple case is just an incremental step.

Member Avatar for boiishuvo

Not really. What I've wrote so far is

if(name_first == null) {
            name_second = new Node(newName, newStudentID, name_first, name_second);
        }
        else {
            if() // if name_first is smaller than the name_second by alphabetical order
        }

This part is what I'm confused with.

Edited by boiishuvo
Member Avatar for JamesCherrill

You have to loop through the existing list to find the right place to make the insertion. This is probably a good time to revise ypuir course notes, or have alook at some of the material on the web, eg
https://en.wikipedia.org/wiki/Linked_list

Member Avatar for boiishuvo 
public void addToList(String newName, int newStudentID){
        public void add(String new_Name, int newStudentID){
        NodeDemo name_First = startPosition.fullNameLink;
        NodeDemo name_Second = startPosition;
        NodeDemo studentId_First = startPosition.studentIDLink;
        NodeDemo studentId_Second = startPosition;

        NodeDemo newnode = new NodeDemo(newName, newStudentID, null, null);

        if(name_first == null)
            name_second = new NodeDemo(newName, newStudentID, name_first, name_second);
        else {
            if(newName.compareToIgnoreCase(name_second.fullNameLink.name) < 0) {
                name_second = new NodeDemo(newName, newStudentID, name_first, name_second.fullNameLink);
                name_second = name_second.fullNameLink;
            }
        }

        if(studentID_first == null)
            studentID_second = new NodeDemo(newName, newStudentID, studentID_first, studentID_second);
        else {
            if(newStudentID > studentID_second.studentIDLink.id) {
                studentID_second = new NodeDemo(newName, newStudentID, studentID_first, studentID_second.studentIDLink);
                studentID_second = studentID_second.studentIDLink;
            }
        }
    }

It still does not work. What I expected is to put the new nodes' name in the alphabetical order and studentID in numerical order. Suggestions?

Edited by boiishuvo
Member Avatar for JamesCherrill

You can only add one Node, so either add it by name, then fix the ID links afterwards, or collect the info on where it fits into both lists before creating the Node.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.