Tuesday, 12 August 2014

Data Structure and Algorithm - Linked List: Common API

As I mentioned that Linked List is regarded as one of most frequently asked interview questions in Data Structure and Algorithm - Sort and Binary Search. One of the most beautiful things of these questions related to Linked List is to tell the interviewers how the candidate understands or grasps the concept and manipulation of pointer, which is regarded not an technical skill but an aptitude.

As I highlight in the following code, passing a pointer to a pointer "**" or passing a pointer "*" to LinkedListElement depends on what the function is to do. Any function is potentially to modify the argument head, a pointer to a pointer to LinkedListElement has to be passed, because the modification has to be made into the argument passed into the function. Otherwise a pointer to LinkedListElement should do the job.

// C Implementation of Linked List
//********************************************************************************
// LinkedListElement.h
#ifndef LINKED_LIST_ELEMENT_H
#define LINKED_LIST_ELEMENT_H

#pragma once

template <typename T>
struct LinkedListElement {
  T data;
LinkedListElement<T>* next = nullptr;

LinkedListElement()
{}
LinkedListElement(const T& t) : data(t)
{}
~LinkedListElement()
{}
};

#endif

// LinkedListAlgo.h
#ifndef LINKED_LIST_ALGO_H
#define LINKED_LIST_ALGO_H

#pragma once

#include "LinkedListElement.h"

template<typename T>
void LL_PushFront(LinkedListElement<T>** head, const T& data)
{
if (*head == nullptr) {
*head = new LinkedListElement<T>(data);
}
else {
LinkedListElement<T>* curHead = *head;
*head = new LinkedListElement<T>(data);
(*head)->next = curHead;
}
}

template<typename T>
void LL_PushBack(LinkedListElement<T>** head, const T& data)
{
if (*head == nullptr) {
*head = new LinkedListElement<T>(data);
}
else {
LinkedListElement<T>* curHead = *head;
while (curHead->next != nullptr) {
curHead = curHead->next;
}
curHead->next = new LinkedListElement<T>(data);
}
}

template<typename T>
void LL_PopFront(LinkedListElement<T>** head)
{
if (head == nullptr || *head == nullptr) {
return;
}

LinkedListElement<T>* temp = *head;
*head = (*head)->next;
delete temp;
}

template<typename T>
void LL_PopBack(LinkedListElement<T>** head)
{
if (head == nullptr || *head == nullptr) {
return;
}
LinkedListElement<T>* prev = *head;
LinkedListElement<T>* curHead = *head;
while (curHead->next != nullptr) {
prev = curHead;
curHead = curHead->next;
}

prev->next = nullptr;
delete curHead;
}

template<typename T>
bool LL_Insert(LinkedListElement<T>** head, size_t pos, const T& data)
{
if (pos == 0) {
LL_PushFront(head, data);
return true;
}

LinkedListElement<T>* curHead = *head;
while (--pos > 0) {
curHead = curHead->next;
if (curHead == nullptr) {
return false;
}
}

LinkedListElement<T>* next = curHead->next;
curHead->next = new LinkedListElement<T>(data);
curHead->next->next = next;
return true;
}

template<typename T>
bool LL_Insert(LinkedListElement<T>** head, const LinkedListElement<T>* pos_node, const T& data)
{
if (head == nullptr || *head == nullptr || pos_node == nullptr) {
return false;
}

if (*head == pos_node) {
LL_PushFront(head, data);
return true;
}

LinkedListElement<T>* prev = nullptr;
LinkedListElement<T>* curHead = *head;
while (curHead != pos_node) {
prev = curHead;
curHead = curHead->next;
if (curHead == nullptr) {
return false;
}
}

prev->next = new LinkedListElement<T>(data);
prev->next->next = curHead;
return true;
}

template<typename T>
bool LL_Erase(LinkedListElement<T>** head, size_t pos)
{
if (head == nullptr || *head == nullptr) {
return false;
}

if (pos == 0) {
LL_PopFront(head);
return true;
}

LinkedListElement<T>* prev = *head;
LinkedListElement<T>* curHead = *head;
while (--pos > 0) {
prev = curHead;
curHead = curHead->next;
if (curHead == nullptr) {
return false;
}
}

prev->next = curHead->next;
delete curHead;
return true;
}

template<typename T>
bool LL_Erase(LinkedListElement<T>** head, const LinkedListElement<T>* pos_node)
{
if (head == nullptr || *head == nullptr || pos_node == nullptr) {
return false;
}

if (*head == pos_node) {
LL_PopFront(head);
return true;
}

LinkedListElement<T>* prev = nullptr;
LinkedListElement<T>* curHead = *head;
while (curHead != pos_node) {
prev = curHead;
curHead = curHead->next;
if (curHead == nullptr) {
return false;
}
}

prev->next = curHead->next;
delete curHead;
return true;
}

template<typename T>
bool LL_GetNth(LinkedListElement<T>* head, size_t pos, T& data)
{
if (head == nullptr) {
return false;
}

while (pos > 0) {
head = head->next;
if (head == nullptr) {
return false;
}
--pos;
}

data = head->data;
return true;
}

template<typename T>
LinkedListElement<T>* LL_GetNth(LinkedListElement<T>* head, size_t pos)
{
if (head == nullptr) {
return nullptr;
}

while (pos > 0) {
head = head->next;
if (head == nullptr) {
return nullptr;
}
--pos;
}

return head;
}

template<typename T>
size_t LL_GetSize(LinkedListElement<T>* head)
{
size_t size = 0;
while (head != nullptr) {
head = head->next;
++size;
}

return size;
}

template<typename T>
void LL_Reverse(LinkedListElement<T>** head)
{
// return if has less than 2 nodes
if (head == nullptr || *head == nullptr || (*head)->next == nullptr) {
return;
}

LinkedListElement<T>* cur = *head;
LinkedListElement<T>* next = nullptr;
LinkedListElement<T>* curHead = nullptr;

while (cur != nullptr) {
next = cur->next;
cur->next = curHead;
curHead = cur;
cur = next;
}

*head = curHead;
}

template<typename T>
void LL_Delete(LinkedListElement<T>** head)
{
if (head == nullptr || *head == nullptr) {
return;
}

LinkedListElement<T>* curHead = *head;
LinkedListElement<T>* temp = nullptr;
while (curHead != nullptr) {
temp = curHead;
curHead = curHead->next;
delete temp;
}

*head = nullptr;
}

/*
 * return -1, if not found
 * 0 - size-1, if found the very first
 */
template<typename T>
ptrdiff_t LL_Find(LinkedListElement<T>* head, const T& val)
{
if (head == nullptr) {
return -1;
}

ptrdiff_t pos = 0;
while (head != nullptr) {
if (head->data == val) {
return pos;
}

head = head->next;
++pos;
}

return -1;
}

template<typename T>
ptrdiff_t LL_Find(LinkedListElement<T>* head, size_t pos, const T& val)
{
if (head == nullptr) {
return -1;
}

while (pos > 0) {
head = head->next;
if (head == nullptr) {
return -1;
}
--pos;
}

return LL_Find(head, val);
}

#endif

// test.cpp
void TestLinkedListAlgo()
{
LinkedListElement<int>* head = nullptr;

// construct list: 20, 12, 10, 9, 9, 8, 7, 15
LL_PushFront(&head, 9);
LL_PushFront(&head, 10);
LL_PushFront(&head, 12);
LL_PushBack(&head, 9);
LL_PushBack(&head, 8);
LL_PushBack(&head, 7);
LL_PushBack(&head, 15);
LL_PushFront(&head, 20);

assert(LL_GetSize(head) == 8);
int val;
assert(LL_GetNth(head, 0, val) == true);
assert(val == 20);
assert(LL_GetNth(head, 1, val) == true);
assert(val == 12);
assert(LL_GetNth(head, 2, val) == true);
assert(val == 10);
assert(LL_GetNth(head, 3, val) == true);
assert(val == 9);
assert(LL_GetNth(head, 4, val) == true);
assert(val == 9);
assert(LL_GetNth(head, 5, val) == true);
assert(val == 8);
assert(LL_GetNth(head, 6, val) == true);
assert(val == 7);
assert(LL_GetNth(head, 7, val) == true);
assert(val == 15);
assert(LL_GetNth(head, 8, val) == false);

LL_PopFront(&head);
assert(LL_GetSize(head) == 7); // 12, 10, 9, 9, 8, 7, 15
LL_PopBack(&head);
assert(LL_GetSize(head) == 6); // 12, 10, 9, 9, 8, 7
LL_Delete(&head);

// constuct list: 18, 25, 30, 11, 10, 9, 5, 20
LL_PushBack(&head, 10);
LL_PushBack(&head, 9);
LL_PushBack(&head, 5);
LL_PushBack(&head, 20);
LL_PushFront(&head, 11);
LL_PushFront(&head, 30);
LL_PushFront(&head, 25);
LL_PushFront(&head, 18);

assert(LL_GetSize(head) == 8);
assert(LL_Insert(&head, 0, 40) == true); // 40, 18, 25, 30, 11, 10, 9, 5, 20
assert(LL_GetSize(head) == 9);
assert(LL_GetNth(head, 0, val) == true);
assert(val = 40);
assert(LL_Insert(&head, 10, 50) == false);
assert(LL_GetSize(head) == 9);
assert(LL_Insert(&head, 9, 50) == true); // 40, 18, 25, 30, 11, 10, 9, 5, 20, 50
assert(LL_GetSize(head) == 10);
assert(LL_GetNth(head, 9, val) == true);
assert(val == 50);
assert(LL_Insert(&head, 3, 100) == true); // 40, 18, 25, 100, 30, 11, 10, 9, 5, 20, 50
assert(LL_GetSize(head) == 11);
assert(LL_GetNth(head, 3, val) == true);
assert(val == 100);

LinkedListElement<int>* elemPtr = LL_GetNth(head, 2); // index starts from 0
assert(elemPtr != nullptr);
assert(elemPtr->data == 25);
assert(LL_GetNth(head, 11) == nullptr);
elemPtr = LL_GetNth(head, 9);
assert(elemPtr != nullptr);
assert(elemPtr->data == 20);
assert(LL_Insert(&head, elemPtr, 70) == true); // 40, 18, 25, 100, 30, 11, 10, 9, 5, 70, 20, 50
assert(LL_GetSize(head) == 12);
elemPtr = LL_GetNth(head, 9);
assert(elemPtr != nullptr);
assert(elemPtr->data == 70);
assert(LL_GetNth(head, 3, val) == true);
assert(val == 100);
assert(LL_GetNth(head, 12, val) == false);
assert(LL_GetSize(head) == 12);

assert(LL_Erase(&head, 0) == true); // 18, 25, 100, 30, 11, 10, 9, 5, 70, 20, 50
assert(LL_GetSize(head) == 11);
elemPtr = LL_GetNth(head, 0);
assert(elemPtr != nullptr);
assert(elemPtr->data == 18);
elemPtr = LL_GetNth(head, 10);
assert(elemPtr != nullptr);
assert(elemPtr->data == 50);
assert(LL_Erase(&head, elemPtr)); // 18, 25, 100, 30, 11, 10, 9, 5, 70, 20
assert(LL_GetSize(head) == 10);
assert(LL_GetNth(head, 10, val) == false);
assert(LL_GetNth(head, 9, val) == true);
assert(val == 20);

LL_PopFront(&head); // 25, 100, 30, 11, 10, 9, 5, 70, 20
assert(LL_GetSize(head) == 9);
elemPtr = LL_GetNth(head, 0);
assert(elemPtr != nullptr);
assert(elemPtr->data == 25);
LL_PopBack(&head); // 25, 100, 30, 11, 10, 9, 5, 70
assert(LL_GetSize(head) == 8);
assert(LL_GetNth(head, 8, val) == false);
assert(LL_GetNth(head, 7, val) == true);
assert(val == 70);

LL_Reverse(&head); // 70, 5, 9, 10, 11, 30, 100, 25
assert(LL_GetSize(head) == 8);
assert(LL_GetNth(head, 0, val) == true);
assert(val == 70);
assert(LL_GetNth(head, 1, val) == true);
assert(val == 5);
assert(LL_GetNth(head, 2, val) == true);
assert(val == 9);
assert(LL_GetNth(head, 3, val) == true);
assert(val == 10);
assert(LL_GetNth(head, 4, val) == true);
assert(val == 11);
assert(LL_GetNth(head, 5, val) == true);
assert(val == 30);
assert(LL_GetNth(head, 6, val) == true);
assert(val == 100);
assert(LL_GetNth(head, 7, val) == true);
assert(val == 25);

assert(LL_Insert(&head, 2, 10) == true); // 70, 5, 10, 9, 10, 11, 30, 100, 25
ptrdiff_t pos = LL_Find(head, 70);
assert(pos == 0);
pos = LL_Find(head, 25);
assert(pos == 8);
pos = LL_Find(head, 30);
assert(pos == 6);
pos = LL_Find(head, 10);
assert(pos == 2);
pos = LL_Find(head, 2, 10);
assert(pos == 0);
pos = LL_Find(head, 3, 10);
assert(pos == 1);
pos = LL_Find(head, 50);
assert(pos == -1);


LL_Delete(&head);
assert(head == nullptr);
assert(LL_GetSize(head) == 0);
}
//********************************************************************************

Bibliography:
[1] http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
[2] Glenn W. Rowe, Data Structure & Algorithm C++, Prentice Hall, 1996
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)