$///$ Singly Linked Lists

#include

using namespace std;

template

class Node

$\{$

public:

T Data;

Node $*$link;

$\}$;

template

class Chain

$\{$

private:

Node $*$first$,*$last;

int len;

public:

Chain$()$;

~Chain$()$;

void Insert$($int$,$ T$)$;

void Delete$($int$,$ T&$)$;

bool Find$($int$,$ T&$)$;

int Search$($T$)$;

void Display$()$;

int Length$()\{$ return len;$\}$

bool isEmpty$()$;

$//$bool isFull$()$;

$\}$;

template

Chain::Chain$()$

$\{$

first $=$ last $=$ NULL;

len$=0$;

$\}$

template

bool Chain ::isEmpty$()$

$\{$

if $($first$==$NULL$)$

return true;

else

return false;

$\}$

template

int Chain::Search$($T Element$)$

$\{$

Node $*$p $=$ first;

int i$=1$;

while$($p $!=$ NULL$)$

$\{$

if$($Element $==$ p$->$Data$)$

return i; $///$ Succ Search

p$=$p$->$link;

i$++$;

$\}$

return $-1$; $///$ Unsucc Search

$\}$

template

bool Chain::Find$($int pos, T &Element$)$

$\{$

if$($pos $<1||$ pos$>$len$)$

$\{$

cout$<<$"Invalid Position....";

return false;

$\}$

Node $*$p$=$first;

for$($int i$=1$;ilink;

Element $=$ p$->$Data;

return true;

$\}$

template

void Chain::Insert$($int pos,T Element$)$

$\{$

Node $*$temp;

temp $=$ new Node;

temp$->$Data $=$ Element;

temp$->$link$=$NULL;

if$($len$==0)$

$\{$

first $=$ last $=$ temp;

$\}$

else

$\{$

if$($pos $==1)$

$\{$

temp$->$link $=$ first;

first $=$ temp;

$\}$

else if$($pos $==$ len$+1)$

$\{$

last$->$link $=$ temp;

last $=$ temp;

$\}$

else

$\{$

Node $*$p$=$first;

for$($int i$=1$;i$<=$pos$-2$;i$++)$

p$=$p$->$link;

temp$->$link $=$ p$->$link;

p$->$link $=$ temp;

$\}$

$\}$

len$++$;

$\}$

template

void Chain::Delete$($int pos, T &Element$)$

$\{$

Node $*$p$,*$q;

p$=$q$=$first;

if$($len$==0)$

$\{$

cout$<<$"Linked List is Empty...";

return;

$\}$

if$($pos$==1)$

$\{$

first$=$first$->$link;

$\}$

else if$($pos$==$len$)$

$\{$

for$($int i$=1$;i$<=$pos$-2$;i$++)$

p$=$p$->$link;

p$->$link$=$NULL;

last$=$p;

$\}$

else

$\{$

for$($int i$=1$;i$<=$pos$-2$;i$++)$

p$=$p$->$link;

q$=$p$->$link;

p$->$link $=$ q$->$link;

$\}$

Element $=$ q$->$Data;

delete q;

len$--$;

$\}$

template

void Chain::Display$()$

$\{$

Node $*$p $=$ first;

while$($p $!=$ NULL$)$

$\{$

cout";

p$=$p$->$link;

$\}$

$\}$

template

Chain::~Chain$()$

$\{$

Node $*$p $=$ first;

while$($p $!=$ NULL$)$

$\{$

first $=$ first$->$link;

cout$<<"$

$"$