implementere doubly linked list basert på headerfiler

[loddetinn]

Holder på å repetere til eksamen i c++ og har møtt på noe jeg ikke forstår bæret av.

Oppgaven er å implementere en doubly linked list basert på følgende header filer:

doublylinkednode.h
#ifndef DOUBLYLINKEDNODE_H
#define DOUBLYLINKEDNODE_H
class DoublyLinkedNode
{
public:
 /* Initialize values as needed */
 DoublyLinkedNode();
 /* Initialize a node with the given values */
 DoublyLinkedNode( int data, DoublyLinkedNode* previous, 
DoublyLinkedNode* next);
 /* Return a pointer to the next node in the list
 * Return NULL if the node is the last in the list */
 DoublyLinkedNode* getNext() const;
 /* Return a pointer to the previous node in the list
 * Return NULL if the node is the first in the list */
 DoublyLinkedNode* getPrevious() const;
 /* Return the data contained in the node */
 int getData() const;
 /* Set the data in the node */
 void setData(int newData);
 /* Set the next node */
 void setNext( DoublyLinkedNode* next);
 /* Set the previous node */
 void setPrevious( DoublyLinkedNode* previous);
private:
 int data;
 DoublyLinkedNode* nextNode;
 DoublyLinkedNode* previousNode;
};
#endif // DOUBLYLINKEDNODE_H

#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H
#include "doublylinkednode.h"
class DoublyLinkedList
{
public: /* Initialize values as needed */
 DoublyLinkedList();
 /* Remove the first element in the list
 * and return a pointer to the element */
 DoublyLinkedNode* removeFirst();
 /* Remove the last element in the list
 * and return a pointer to the element */
 DoublyLinkedNode* removeLast();
 /* Return a pointer to the first occurrence of the given 
 * value in the list */
 DoublyLinkedNode* find( int val ) const;
 /* Remove the first occurrence of the given value in the list
 * and return a pointer to the element */
 DoublyLinkedNode* remove( int val );
 /* Add a node with the given value to the end of the list */
 void add( int val );
 /* return a pointer to the first node in the list */
 DoublyLinkedNode* first() const;
 /* Return a pointer to the last node in the list */
 DoublyLinkedNode* last() const;
 /* Return true if the given value is found in the list, 
 * false otherwise */
 bool contains( int val ) const;
 /* Return true if the list is empty, false otherwise */
 bool isEmpty() const;
 /* Return the number of elements in the list */
 int size() const;
private:
 DoublyLinkedNode *head;
 int numberOfElements;
};
#endif // DOUBLYLINKEDLIST_H

Er det noen som kunne hjulpet meg her?
Det beste hadde vært om noen kunne gjort det og lagt en liten kommentar til koden, dersom noen ville tatt på seg bryet å gjøre dette, betaler jeg selvsagt noen hundre kroner for det.

[morslilleole]

Først av alt bør du lese om hva en linked list er. Anbefaler deg til å ta deg tid til å implementere den. Du vil få en mye bedre forståelse av hva en linked list er og hvordan den fungerer

Prinsippet er :

• Listen består av noder ( DoublyLinkedNode )
• Hver node har to pekere ( nextNode og previousNode)
• Du går fra en node til neste node ved å bruke en av pekerne jeg nevnte over
• Selve listen ( DoublyLinkedList ) har en peker til første node ( head )

Litt hjelp på veien :

 

First()

1. Returnerer bare head

Find( n )

1. Start i head( element 0 ),
2. Bruker pekeren til å gå til neste node ( 1 ),
3. Fortsett helt til du kommer til node som inneholder veriden n

 

Remove( n )

1. Gå til første node som inneholder n. ( Her kan du bruke Find( n ) for å holde koden din tørr )
2. Koper adressen til neste og forrige node.
3. Naviger tilbake til forrige node
4. Her setter du pekeren til neste node til å peke til samme stedet som neste-pekeren du kopierte fra node n
5. Naviger til neste node ( noden som kom etter den du sluttet )
6. Set forrige-pekeren til å peke til samme stedet som forrige-pekeren til noden du slettet.

EDIT : Fikset tullefeil. Takk til etse, burde lest kommentarene bedre!

Endret 4. mai 2014 av morslilleole

[etse]

Litt feil spesifisert over her med tanke på find og remove.

 

Find( n ):

Finn det første elementet i listen som har verdien N, returner pekeren til denne.

 

Remove( n ):

Finn det første elementet som inneholder verdien N (kanskje bruke find til dette?) - fjern denne fra listen slik morslilleole nevner over her.

Endret 4. mai 2014 av etse