Singly-linked list/Element removal: Difference between revisions

Content added Content deleted

Inline

@@ Line 387: / Line 387: @@
 After 1st removal : 1 -> 3
 After 2nd removal : 1
+</pre>
+=={{header|Phix}}==
+Note that singly-linked lists are a bit alien to Phix, since the core sequence type is so versatile.
+While [[Singly-linked_list/Traversal#Phix]] inserts at the end, I thought I'd mix things up and try an in-order insert here
+and then mix them up again and remove items in a random order. Obviously remove_item() forms the meat
+of the task requirement; insert_inorder(), show(), and test() aren't really and can be skipped.
+<lang Phix>enum NEXT,DATA
+sequence sll = {}
+integer sll_head = 0,
+        sll_free = 0
+procedure insert_inorder(object data)
+    if length(sll)=0 or sll_head=0 then
+        sll = {{0,data}}
+        sll_head = 1
+        sll_free = 0
+    else
+        integer this = sll_head, next, flag = 0
+        object node = 0
+        while 1 do
+            next = sll[this][NEXT]
+            if data<sll[this][DATA] then
+                flag = 1
+                node = sll[this]
+            elsif next=0 then
+                flag = 2
+                node = {0,data}
+            end if
+            if flag then
+                if sll_free then
+                    next = sll_free
+                    sll_free = sll[next][NEXT]
+                    sll[next] = node
+                else
+                    sll = append(sll,node)
+                    next = length(sll)
+                end if
+                sll[this][NEXT] = next
+                if flag=1 then
+                    sll[this][DATA] = data
+                end if
+                exit
+            end if
+            this = next
+        end while
+    end if
+end procedure
+procedure remove_item(object data)
+    integer idx = sll_head, prev
+    while idx do
+        if sll[idx][DATA]=data then
+            if idx=sll_head then
+                sll_head = sll[idx][NEXT]
+            else
+                sll[prev][NEXT] = sll[idx][NEXT]
+            end if
+            sll[idx][NEXT] = sll_free
+            sll[idx][DATA] = 0
+            sll_free = idx
+            exit
+        end if
+        prev = idx
+        idx = sll[idx][NEXT]
+    end while
+end procedure
+procedure show()
+integer idx = sll_head
+sequence list = {}
+    while idx do
+        list = append(list,sll[idx][DATA])
+        idx = sll[idx][NEXT]
+    end while
+    ?list
+end procedure
+enum ADD,REMOVE
+procedure test(integer mode, sequence list)
+    ?{{"add","remove"}[mode],list}
+    for i=1 to length(list) do
+        if mode=ADD then
+            insert_inorder(list[i])
+        else
+            remove_item(list[i])
+        end if
+        show()
+    end for
+end procedure
+sequence list = {"1","2","3","4"}
+test(ADD,shuffle(list))
+test(REMOVE,shuffle(list))</lang>
+{{out}}
+<pre>
+{"add",{"4","2","3","1"}}
+{"4"}
+{"2","4"}
+{"2","3","4"}
+{"1","2","3","4"}
+{"remove",{"1","3","2","4"}}
+{"2","3","4"}
+{"2","4"}
+{"4"}
+{}
 </pre>