Design and implement you own linked list class of strings (this should not be a
ID: 643904 • Letter: D
Question
Design and implement you own linked list class of strings (this should not be a class template). The class should have the following methods:
append : adds a new element to the end of the list
insert: adds a new element at a position in the list. The position is an integer value (not an iterator).
delete: deletes a node at a given position. The position is an integer value.
constructor & copy constructor
destructor: must delete all of the nodes
Your linked list can be either a singly-linked list or doubly-linked list. There is a singly-linked list shown in your book and we discussed a doubly-linked list in class.
Here is the source code that will be used to create the linked list class.
slist.h
//
//
// simplified list class
//
// Described in Chapter 9 of
// Data Structures in C++ using the STL
// Published by Addison-Wesley, 1997
// Written by Tim Budd, budd@cs.orst.edu
// Oregon State University
//
//
namespace cist2362 {
template <class T> class list;
template <class T> struct link;
template <class T> class listIterator {
typedef listIterator<T> iterator;
public:
// constructor
listIterator (list<T> * tl, link<T> * cl)
: theList(tl), currentLink(cl) { }
// iterator protocol
T & operator * ()
{ return currentLink->value; }
void operator = (iterator & rhs)
{ theList = rhs.theList; currentLink = rhs.currentLink; }
bool operator == (const iterator rhs) const
{ return currentLink == rhs.currentLink; }
iterator & operator ++ (int)
{ currentLink = currentLink->nextLink; return * this; }
iterator operator ++ ();
iterator & operator -- (int)
{ currentLink = currentLink->prevLink; return * this; }
iterator operator -- ();
protected:
list <T> * theList;
link <T> * currentLink;
friend class list<T>;
};
template <class T>
class list {
public:
// type definitions
typedef T value_type;
typedef listIterator<T> iterator;
// constructor and destructor
list () : firstLink(0), lastLink(0) { }
list (list<T> & x) : firstLink(0), lastLink(0) { }
~ list ();
// operations
bool empty () { return firstLink == 0; }
int size();
T & back () { return lastLink->value; }
T & front () { return firstLink->value; }
void push_front(T &);
void push_back(T &);
void pop_front ();
void pop_back ();
iterator begin () { return iterator (this, firstLink); }
iterator end () { return iterator (this, 0); }
void sort ();
void insert (iterator &, T &);
void erase (iterator & itr) { erase (itr, itr); }
void erase (iterator &, iterator &);
protected:
link <T> * firstLink;
link <T> * lastLink;
};
template <class T> class link {
private:
link (T & v) : value(v), nextLink(0), prevLink(0) { }
T value;
link<T> * nextLink;
link<T> * prevLink;
// allow lists to see element values
friend class list<T>;
friend class listIterator<T>;
};
template <class T> int list<T>::size ()
// count number of elements in collection
{
int counter = 0;
for (link<T> * ptr = firstLink; ptr != 0; ptr = ptr->nextLink)
counter++;
return counter;
}
template <class T> void list<T>::push_front (T & newValue)
// add a new value to the front of a list
{
link<T> * newLink = new link<T> (newValue);
if (empty())
firstLink = lastLink = newLink;
else {
firstLink->prevLink = newLink;
newLink->nextLink = firstLink;
firstLink = newLink;
}
}
template <class T> void list<T>::pop_front()
// remove first element from linked list
{
link <T> * save = firstLink;
firstLink = firstLink->nextLink;
if (firstLink != 0)
firstLink->prevLink = 0;
else
lastLink = 0;
delete save;
}
template <class T> list<T>::~list ()
// remove each element from the list
{
link <T> * first = firstLink;
while (first != 0) {
link <T> * next = first->nextLink;
delete first;
first = next;
}
}
template <class T> listIterator<T> listIterator<T>::operator ++ ()
// postfix form of increment
{
// clone, then increment, return clone
listIterator<T> clone (theList, currentLink);
currentLink = currentLink->nextLink;
return clone;
}
template <class T>
void list<T>::insert (listIterator<T> & itr, T & value)
// insert a new element into the middle of a linked list
{
link<T> * newLink = new link<T>(value);
link<T> * current = itr->currentLink;
newLink->nextLink = current;
newLink->prevLink = current->prevLink;
current->prevLink = newLink;
current = newLink->prevLink;
if (current != 0)
current->nextLink = newLink;
}
template <class T>
void list<T>::erase (listIterator<T> & start, listIterator<T> & stop)
// remove values from the range of elements
{
link<T> * first = start.currentLink;
link<T> * prev = first->prevLink;
link<T> * last = stop.currentLink;
if (prev == 0) { // removing initial portion of list
firstLink = last;
if (last == 0)
lastLink = 0;
else
last->prevLink = 0;
}
else {
prev->nextLink = last;
if (last == 0)
lastLink = prev;
else
last->prevLink = prev;
}
// now delete the values
while (start != stop) {
listIterator<T> next = start;
++next;
delete start.currentLink;
start = next;
}
}
}
sListDriver.cpp
#include <iostream>
#include <list>
using namespace std;
class Widget {
};
int main() {
list<int> list_one;
list<Widget*> mylist;
return 0;
}
Explanation / Answer
public class LinkedList {
/**
* Construct the list
*/
public LinkedList( ) {
header = new ListNode( null );
}
/**
* Test if the list is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return header.next == null;
}
/**
* Make the list logically empty.
*/
public void makeEmpty( ) {
header.next = null;
}
/**
* Return an iterator representing the header node.
*/
public LinkedListIterator zeroth( ) {
return new LinkedListIterator( header );
}
/**
* Return an iterator representing the first node in the list.
* This operation is valid for empty lists.
*/
public LinkedListIterator first( ) {
return new LinkedListIterator( header.next );
}
/**
* Insert after p.
* @param x the item to insert.
* @param p the position prior to the newly inserted item.
*/
public void insert( Object x, LinkedListIterator p ) {
if( p != null && p.current != null )
p.current.next = new ListNode( x, p.current.next );
}
/**
* Return iterator corresponding to the first node containing an item.
* @param x the item to search for.
* @return an iterator; iterator is not valid if item is not found.
*/
public LinkedListIterator find( Object x ) {
ListNode itr = header.next;
while( itr != null && !itr.element.equals( x ) )
itr = itr.next;
return new LinkedListIterator( itr );
}
/**
* Return iterator prior to the first node containing an item.
* @param x the item to search for.
* @return appropriate iterator if the item is found. Otherwise, the
* iterator corresponding to the last element in the list is returned.
*/
public LinkedListIterator findPrevious( Object x ) {
ListNode itr = header;
while( itr.next != null && !itr.next.element.equals( x ) )
itr = itr.next;
return new LinkedListIterator( itr );
}
/**
* Remove the first occurrence of an item.
* @param x the item to remove.
*/
public void remove( Object x ) {
LinkedListIterator p = findPrevious( x );
if( p.current.next != null )
p.current.next = p.current.next.next; // Bypass deleted node
}
// Simple print method
public static void printList( LinkedList theList ) {
if( theList.isEmpty( ) )
System.out.print( "Empty list" );
else {
LinkedListIterator itr = theList.first( );
for( ; itr.isValid( ); itr.advance( ) )
System.out.print( itr.retrieve( ) + " " );
}
System.out.println( );
}
private ListNode header;
// In this routine, LinkedList and LinkedListIterator are the
// classes written in Section 17.2.
public static int listSize( LinkedList theList ) {
LinkedListIterator itr;
int size = 0;
for( itr = theList.first(); itr.isValid(); itr.advance() )
size++;
return size;
}
public static void main( String [ ] args ) {
LinkedList theList = new LinkedList( );
LinkedListIterator theItr;
int i;
theItr = theList.zeroth( );
printList( theList );
for( i = 0; i < 10; i++ ) {
theList.insert( new Integer( i ), theItr );
printList( theList );
theItr.advance( );
}
System.out.println( "Size was: " + listSize( theList ) );
for( i = 0; i < 10; i += 2 )
theList.remove( new Integer( i ) );
for( i = 0; i < 10; i++ )
if( ( i % 2 == 0 ) == ( theList.find( new Integer( i ) ).isValid( ) ) )
System.out.println( "Find fails!" );
System.out.println( "Finished deletions" );
printList( theList );
}
}
// LinkedListIterator class; maintains "current position"
//
// CONSTRUCTION: Package visible only, with a ListNode
//
// ******************PUBLIC OPERATIONS*********************
// void advance( ) --> Advance
// boolean isValid( ) --> True if at valid position in list
// Object retrieve --> Return item in current position
/**
* Linked list implementation of the list iterator
* using a header node.
* @author Mark Allen Weiss
* @see LinkedList
*/
public class LinkedListIterator {
/**
* Construct the list iterator
* @param theNode any node in the linked list.
*/
LinkedListIterator( ListNode theNode ) {
current = theNode;
}
/**
* Test if the current position is a valid position in the list.
* @return true if the current position is valid.
*/
public boolean isValid( ) {
return current != null;
}
/**
* Return the item stored in the current position.
* @return the stored item or null if the current position
* is not in the list.
*/
public Object retrieve( ) {
return isValid( ) ? current.element : null;
}
/**
* Advance the current position to the next node in the list.
* If the current position is null, then do nothing.
*/
public void advance( ) {
if( isValid( ) )
current = current.next;
}
ListNode current; // Current position
}
// Basic node stored in a linked list
// Note that this class is not accessible outside
// of package weiss.nonstandard
class ListNode {
// Constructors
public ListNode( Object theElement ) {
this( theElement, null );
}
public ListNode( Object theElement, ListNode n ) {
element = theElement;
next = n;
}
public Object element;
public ListNode next;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.