Linked Lists problem

So if your node has five elements in it, and you call delete(10000), well, hope you didn't like that computer very much. This is probably what you mean by throwing an exception for an empty node. Maybe.

And to avoid repeats, in your insert code, just check to see whether the thing you're inserting is equal to the list element you're looking at. If so, complain loudly.

Anything (and everything) about linked lists depends on some node->next being NULL.

So any traversal MUST include that as a condition if nothing else.
If you're counting n, then your loop would be

Code:

---

while ( p != NULL && i < n ) {
  i++;
  p = p->next;
}
if ( p == NULL ) {
  // mmm, fell off the end of the list, I wonder what that means...
}

---

so tell me if im understanding this correctly..

first off.. wouldnt the highlighted text kind of be a check for falling off the end of the list?

and secondly, if i am completely wrong, i added the blue text which is basically where i think id add in the other form of refuting the falling off

Code:

---

/* SLLinsert: inserts a new entry into the list
 * Pre conditions: The list created, not full, x is a valid list entry, p is a valid position
 * Post conditions: x has successfully been inserted into position p in list
 */

void SLLinsert(Position p, ListEntry x, List *list) {
    ListNode *newNode, *current;
   
    if (p < 0 || p > list->count)
          Error("Attempt to insert in a position not in the list.");
    else {
          newNode = MakeListNode(x);
          if (p == 0) {
              newNode->next = list->head;
              list->head = newNode;
              }
          while ( p != NULL && i < n ) {
              i++;
              p = p->next;
              }
          if ( p == NULL ) {
              //Not sure how what I would do with p after finding it is null, other than just
              //terminating it..
          }
          else {
              SetPosition(p-1, list, &current);
              newNode->next = current->next;
              current->next = newNode;
              }
          list->count++;
          }
}

---

The bit in red will keep things straight (assuming you keep count current and accurate and all of that). And if the bit in blue triggers, you give the same error message. (It shouldn't ever happen, so actually you could make this message "This can't happen." This way you can identify bugs vs. user idiocy.)

Notice how that bit is completely and utterly missing from your delete function.

Yea I figured the red was going to be able to handle it, but wasn't positive. And with you mentioning that I am missing that from my delete function, are you insinuating that it is such a situation that I don't need it, hence why I don't need it, or that I am missing it, and SHOULD have it in there (the red text)

Since I've mentioned (and others) several times that you have no protection in your delete function from walking off the end of the list, and the red part is what keeps you from walking off the end of the list, then I would expect that you would want to make sure the red part is in your delete function.

Sorry, I wasn't kidding when I mentioned I was slow at this.. heh. Hows this look;

Code:

---

                                        // If the node is not the starting or the last one
void delete(int n) {          //deletes the nth position node of the linked list
    if (p < 0 || p > n->count)
          Error("Attempting to delete what isn't there.");
    else {
          node *p;                //node - type pointer to traverse the linked list
          int i = 1;
          while(i < n-1) {
              p = p->next;      //points to next node
              ++i;
              }
          }
                                        //Now p is at the node previous to the node to be deleted
    node *q;                      //declares another pointer
    q = p->next;                //q is next to q
    p->next = q->next;
    free(q);
}

---

Quote:

---

n->count

---

int has no members

Code:

---

node *p;                //node - type pointer to traverse the linked list
int i = 1;
while(i < n-1) {
      p = p->next;/* p is not initialized */

---

using the list function I already had made a lot more sense than using n, so I changed that.. but im nto really sure how I should go about initializing p.. i thought it was already

Code:

---

                                        // If the node is not the starting or the last one
void delete(int n) {          //deletes the nth position node of the linked list
    if (p < 0 || p > list->count) //just use the list function, not sure why i didn't before
          Error("Attempting to delete what isn't there.");
    else {
          node *p;                //node - type pointer to traverse the linked list
          int i = 1;
          while(i < n-1) {
              p = p->next;      //points to next node
              ++i;
              }
          }
                                        //Now p is at the node previous to the node to be deleted
    node *q;                      //declares another pointer
    q = p->next;                //q is next to q
    p->next = q->next;
    free(q);
}

---

Code:

---

    if (p < 0 || p > list->count) //just use the list function, not sure why i didn't before
          Error("Attempting to delete what isn't there.");

---

unless you have a variable p that is global, and then hide it with a local variable, this is very wrong.

Alright.. so far I have this which I think is for the most part.. correct.

Code:

---

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

struct SLL {
  int val;
  struct SLL * next;
};

typedef struct SLL element;

int main() {
  element * curr, * head;
  int i;

  head = NULL;

  for(i=1;i<=10;i++) {
      curr = (element *)malloc(sizeof(element));
      curr->val = i;
      curr->next  = head;
      head = curr;
  }

  curr = head;

  while(curr) {
      printf("%d\n", curr->val);
      curr = curr->next ;
  }
}


/* SLLinsert: inserts a new entry into the list
 * Pre conditions: The list created, not full, x is a valid list entry, p is a valid position
 * Post conditions: x has successfully been inserted into position p in list
 */

void SLLinsert(Position p, ListEntry x, List *list) {
    ListNode *newNode, *curr;
   
    if (p < 0 || p > list->count)
          Error("Attempt to insert in a position not in the list.");
    else {
          newNode = MakeListNode(x);
          if (p == 0) {
              newNode->next = list->head;
              list->head = newNode;
              }
          else {
              SetPosition(p-1, list, &curr);
              newNode->next = curr->next;
              curr->next = newNode;
              }
          list->count++;
          }
}

---

But I am having trouble with the deletion process..as you can all see.. this is where I am at at this point.. let me know what you think

Code:

---

void SLLdelete(nodeT **listP, elementT value) {
      nodeT *currP, *prevP;

      /* For 1st node, indicate there is no previous. */
      prevP = NULL;

      /*
      * Visit each node, maintaining a pointer to
      * the previous node we just visited.
      */
      for (currP = *listP;
            currP != NULL;
            prevP = currP, currP = currP->next) {

        if (currP->element == value) {  /* Found it. */
          if (prevP == NULL) {
            /* Fix beginning pointer. */
            *listP = currP->next;
          } else {
            /*
            * Fix previous node's next to
            * skip over the removed node.
            */
            prevP->next = currP->next;
          }

          /* Deallocate the node. */
          free(currP);

          /* Done searching. */
          return;
        }
      }
    }

---

I am pretty sure this works when you are deleting the first node of the list.. but does it work with all nodes, or just the when it is the first? and i still do not have a call for the error..

You've created a list of 10 elements, so try
- deleting the first
- deleting the last
- deleting one in the middle
Then priinting the result.

If it looks OK, then it probably works.

my professor is trying to have us do this analytically and not use a compiler to check for our mistakes, so I am basically doing this in notepad and trying to see if i notice anything that would go a rye.

I do have it in position to create a list of 10 elements, and i'm fairly confident about it being able to insert an element, and i am still also fairly confident that with my delete function, it would delete the first node, but i would i have to add more to the code, so it pays more attention to every possible deleting situation?

Well if you're reasonably happy about both ends of the list, then I'd say you're done.

lol but i'm not even a fraction knowledgeable about this stuff as much as you guys who help me! thats why im just asking you're opinion if you agree! lol :)