DeleteDuplicates() from Singly Linked List - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

DeleteDuplicates() from Singly Linked List

patrickstar85patrickstar85 Posts: 7Member
Hey there, i was thinking about deleting the duplicates from an unsorted SLL, but i wasn't able to get it right. does anyone have some tips for me?

Here's the Code so far:
[code]PROGRAM SLList;

USES
WinCrt;

TYPE
Node=^NodeRecord;
NodeRecord=RECORD
val:STRING;
next:NODE;
END;

List=Node;

{**************************************************************************}
FUNCTION NewList:List;
BEGIN
newList:=NIL;
END;
{**************************************************************************}
FUNCTION NewNode(val:STRING):Node;
VAR
n:Node;
BEGIN
New(n);
IF n=NIL THEN
WriteLn('Out of Memory')
ELSE BEGIN
n^.val:=val;
n^.next:=NIL;
END;
NewNode:=n;
END;
{**************************************************************************}
PROCEDURE Prepend(VAR l:List;val:STRING);
VAR
n:Node;
BEGIN
n:=NewNode(val);
n^.next:=l;
l:=n;
END;
{**************************************************************************}
PROCEDURE WriteList(l:List);
VAR
n:Node;
BEGIN
n:=l;
WHILE n<>NIL DO BEGIN
Write(n^.val,' ');
n:=n^.next;
END;
END;
{**************************************************************************}
PROCEDURE DisposeList(VAR l:List);
VAR
n:Node;
BEGIN
WHILE l<>NIL DO BEGIN
n:=l^.next;
Dispose(l);
l:=n;
END;
END;
{**************************************************************************}
PROCEDURE DeleteDuplicates(VAR l:List);
VAR
n:Node; (*???*)
BEGIN
(*?????????*)
END;
{**************************************************************************}

VAR
li,l:List;
i:INTEGER;

BEGIN
l:=NewList;
Prepend(l,'test');
Prepend(l,'test');
Prepend(l,'hello');
Prepend(l,'test');
Prepend(l,'lol');
Prepend(l,'hello');
Prepend(l,'lol');
Prepend(l,'test');
Prepend(l,'hello');
WriteList(l);
WriteLn;
DeleteDuplicates(l);
WriteList(l);
END.[/code]

Best Regards
-Patrick

Comments

  • patrickstar85patrickstar85 Posts: 7Member
    alright, now i found out how i can delete duplicates, but therefore the list must be sorted. Does anyone have a good algorithm to sort the list, before kicking out duplicates?

    [code]PROCEDURE DeleteDuplicates(l:List);
    VAR
    tn,next:Node;
    tl:List;
    BEGIN
    IF l<>NIL THEN BEGIN
    tl:=l;
    WHILE (tl^.next<>NIL) DO BEGIN
    tn:=tl^.next;
    IF tl^.val=tn^.val THEN BEGIN
    next:=tn^.next;
    Dispose(tn);
    tl^.next:=next;
    END ELSE
    tl:=tl^.next;
    END;
    l:=tl;
    END ELSE BEGIN
    Writeln('Liste leer');
    END;
    END;[/code]
  • _Atex__Atex_ Posts: 163Member
    : alright, now i found out how i can delete duplicates, but therefore
    : the list must be sorted. Does anyone have a good algorithm to sort
    : the list, before kicking out duplicates?
    :
    : [code]: PROCEDURE DeleteDuplicates(l:List);
    : VAR
    : tn,next:Node;
    : tl:List;
    : BEGIN
    : IF l<>NIL THEN BEGIN
    : tl:=l;
    : WHILE (tl^.next<>NIL) DO BEGIN
    : tn:=tl^.next;
    : IF tl^.val=tn^.val THEN BEGIN
    : next:=tn^.next;
    : Dispose(tn);
    : tl^.next:=next;
    : END ELSE
    : tl:=tl^.next;
    : END;
    : l:=tl;
    : END ELSE BEGIN
    : Writeln('Liste leer');
    : END;
    : END;[/code]:
    :


    There is no need to sort an array to delete duplicates, if you need to sort some stuff then look at one of my posts I wrote a few days ago, it has some simple sorting implemented there. To delete a duplicate item follow the this pseudocode:
    1. for i:=1 to (length of array)-1 do
    2. for j:=2 to length of array do
    3. if element[i]=element[j] then: delete element[j];
Sign In or Register to comment.