Ordered Linked Lists

• This one is like a normal linked list, except that the values inside are ordered (sorted).
• We have 4 basic operations in an ordered linked list.
  1. insert data in sorted order
  2. search operation
  3. deleting from linked list (targeted deleting, so linked list should be searched first)
  4. copy the object

class List(){
	private:
		Node* head;
	public:
		// the default constructor
		List(){ head = nullptr;}
		// default destructor
		~List(){delete head;}
		
		// insert data function
		void insertData(int);
		// search operation
		bool dataExists(int);
		// delete function (returns bool, since it's a targeted delete)
		bool delete(int);
		// our copy constructor
		List(const List&);
		// our operator constructor
		List& operator=(const List&)
}

The search function

bool List::dataExists(int d){
	// make a copy of the head (we don't want to actually edit head)
	Node* p = head;
	// keep searching while p is not null and p doesn't point to our desired d
	// we have to realize that since we have a sorted linked list, we can just
	// stop searching once we read a value of d that is greater than our d 
	while (p!= nullptr && p->getData() <= d){
		if (p->getData() == d)
			return true;
		else
			p = p->getNext();
	}
	// if the loop ended without returning true, it means the d wasnt found
	return false;
}

The insert function

1. I create a new object (using the specific constructor)
2. Look for the exact location to insert the node
   1. traverse the linked list to see
3. next of the prev should point to my new object, next of my object points to my nextp

• this is an ordered insert function
• I need to first find out the exact location to put my new data
  • I need two pointers, one for the previous prev, one for the next nextp
  • next of the prev should point to my new object, next of my object points to my nextp

void List::insertData(ind d){
	Node* n = new Node(d); // I know have the new object
	Node* p = head; // our "current" pointer
	Node* prev = NULL; // 
	
	while (p!= NULL && p->getDAta() < d){
		// while I haven't reached my position, prev gets p, p gets next
		prev = p;
		p = p->getNext();
	}
	n->setNext() = p;
	
	if (prev == null) // I need to update head itself if its at the start/empty list
		head = n;
	else
		prev->setNext(n);
}

The delete function

• Say we want to delete the object with data value 2
  • I need a pointer p (to traverse) and a pointer prev (to point to previous)

1. search for the node
2. secure the next of our node by making the next of previous equal to next of our node
3. relink the list

bool List::delete(int d){
	Node* p = head; // this is our traversal "current" pointer
	Node* prev = NULL:
	
	// search for node
	while (p != NULL && p->getData() != d){
		if (p->getData() > d)
			return false; // it means our data does not exist
		prev = p;
		p = p->getNext();
	}
	// at this opint, i have a pointer pointing to our node, and also another
	// pointer prev pointing to the one before (nice position)
	if (p == NULL)
		// everything in the linked list is smaller than the value i'm looking for
		return false;
	if (prev == NULL)
		head = p->getNext();
	else
		prev->setNext(p->getNext());
	
	// I need to cut the p's link so i don't delete the whole list
	p->setNext(NULL);
	delete p;
}