Linked Lists

[wasteproduct]

Hi,
I'm having trouble with my assignment..

I know how to add a node at the end of the lists,
but I can't see the way to add a node at any space where I want.

Also, I need to make a function that flips the whole lists.

I'll be so happy with and appreciate any help.

Here's what I've got so far.

  #include "stdafx.h"
#include <iostream>
using namespace std;
void add(char *addname, int entry);
void output();
void reverse();
struct person
{
	char *name;
	person *next;
	person *prev;
};
person *newPerson;
person *head = NULL;
person *currentPerson;
int main()
{
	newPerson = new person;
	newPerson->next = NULL;
	head = newPerson;
	
	add("Adam", 1);
	add("Ben", 2);
	add("Chris", 3);
	add("Derek", 4);
	add("Earl", 3);
	output();
	cout << endl << endl;
	delete newPerson;
    return 0;
}
void add(char *addname, int entry)
{
	person *newFace = new person;
	newFace->name = addname;
	newFace->next = NULL;
	newPerson->next = newFace;
	newPerson = newFace;
}
void output()
{
	currentPerson = head->next;
	while (currentPerson != NULL)
	{
		cout << currentPerson->name << endl;
		currentPerson = currentPerson->next;
	}
}
void reverse()
{

}

[dhayden]

Line 11: prev implies that this is a doubly linked list, but you never access this member anywhere in the code. So should this be a doubly or singly linked list?

add() will add at the end of the list, but only because newPerson points there. I suggest that you rename newPerson to be tail, which is much more common.

Consider using a for loop in output:

void
output()
{
    for (cur = head->next; cur != NULL; cur = cur->next) {
        cout << cur->name << endl;
    }
}

I think this is much clearer because all of the loop logic is contained within the for() statement and the "what to do each time through the loop" logic is in the body of the loop.

To insert at the n^th position, create a local person pointer called prev and advance prev to the n-1^th item of the list. Then new item will go right after prev.

[wasteproduct]

I think it is okay to use either singly or doubly linked list.

Can you please explain more in detail about inserting node at the n^th position? I'm still confused.

[dhayden]

Here is code to insert at position N using a slightly different list.

// Attempt to insert data at position pos (where pos==0 means the
// head) If pos > list size then insert at end. Returns the actual
// position where it was inserted.
unsigned List::addNth(int data, unsigned pos)
{
    Node *newNode = new Node;
    newNode->data = data;
    
    Node *prev = nullptr;	// previous node
    Node *cur;			// current node
    unsigned p;			// position where newNode inserted

    // Walk prev and cur down the list until you reach the end or
    // the pos'th node
    for (cur=head, p=0; p < pos && cur; prev = cur, cur = cur->next) {
	++p;
    }

    if (prev) {
	newNode->next = cur;
	prev->next = newNode;
    } else {
	newNode->next = head;
	head = newNode;
    }
    return p;
	
}