Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.