How to remove the 'k' number of elements in a linked list.

[philip1999]

How to remove the 'k' number of elements in a linked list.

I search the many sites on the internet but found nothing.

Can anyone please give the link to the site or please explain how to remove 'k' elements from a list.

description: removes the first k elements from the
calling list which are used to form a new list
which is then returned.

if n is the length of the given list, we have the
	   *		following boundary conditions:
	   *
	   *		  if k==0:
	   *			    calling list unchanged and an empty list returned
	   *		  if k>=n:
	   *			    calling becomes empty and a list containing
	   *			    all elements previously in lst is returned.
	   *
	   *		examples:
	   *
	   *		  EX1:  lst:  [2, 3, 9, 7, 8]
	   *			k:    3
	   *
	   *			call:
	   *
	   *			  List<int> * pre = lst.prefix(3);
	   *
	   *			after call:
	   *			   lst:  [7, 8]
	   *			   returned list (prefix):  [2, 3, 9]
	   *
	   *		  EX2  lst:  [2, 3, 9, 7, 8]
	   *			k:    0
	   *
	   *		  call:
	   *
	   *			  List<int> * pre = lst.prefix(3);
	   *
	   *			after call:
	   *			   lst:  [2, 3, 9, 7, 8]  (unchanged)
	   *			   returned list:  []
	   *
	   *		  EX3  lst:  [2, 3, 9, 7, 8]
	   *			k:    5
	   *
	   *		  call:
	   *
	   *			  List<int> * pre = lst.prefix(5);
	   *
	   *			after call:
	   *			   lst:  []
	   *			   returned list:  [2, 3, 9, 7, 8]

struct Node
	{
		T data;
		Node *next;
        };
        Node *front;
	Node *back;

        List() {
		front = NULL;
		back = NULL;
	}

My function is

void insert_sorted(const T &x)
	{

	}

[keskiverto]

How to remove the 'k' number of elements in a linked list.

Lets see if I understand the task:

There is a list. It might have some elements (aka nodes).

I want to remove 5 elements from it?
From where? Beginning? End? Middle? Random elements?


PS. Why do you mention insertion? Are we not removing something here?

[philip1999]

@keskiverto

if n is the length of the given list, we have the
	   *		following boundary conditions:
	   *
	   *		  if k==0:
	   *			    calling list unchanged and an empty list returned
	   *		  if k>=n:
	   *			    calling becomes empty and a list containing
	   *			    all elements previously in lst is returned.
	   *
	   *		examples:
	   *
	   *		  EX1:  lst:  [2, 3, 9, 7, 8]
	   *			k:    3
	   *
	   *			call:
	   *
	   *			  List<int> * pre = lst.prefix(3);
	   *
	   *			after call:
	   *			   lst:  [7, 8]
	   *			   returned list (prefix):  [2, 3, 9]
	   *
	   *		  EX2  lst:  [2, 3, 9, 7, 8]
	   *			k:    0
	   *
	   *		  call:
	   *
	   *			  List<int> * pre = lst.prefix(3);
	   *
	   *			after call:
	   *			   lst:  [2, 3, 9, 7, 8]  (unchanged)
	   *			   returned list:  []
	   *
	   *		  EX3  lst:  [2, 3, 9, 7, 8]
	   *			k:    5
	   *
	   *		  call:
	   *
	   *			  List<int> * pre = lst.prefix(5);
	   *
	   *			after call:
	   *			   lst:  []
	   *			   returned list:  [2, 3, 9, 7, 8]

[jonnin]

so, delete from the 'top/front'.

ok.

can you write a method that removes 1 item from the top?
probably
if(head)
{
temp = head.
head = head -> next
delete temp
}

and then you can call that in a loop, for however many you have. if the list is empty, it does nothing, so you don't even have to check all that ... they ask for 5 deleted, it has 3 in it, comes back empty. has 5, delete 3, the last 2 are what is left.

[keskiverto]

description: removes the first k elements from the
calling list which are used to form a new list
which is then returned.

Knowing what to do does help.

jonnin did describe one approach:
repeat k times:
[take one element at a time from head of list and append it to the tail of new list]


The other approach is to split the list after the kth element.

Example: [a-b-c-d-e] lst.front=a lst.back=e
k=3

pre.front=a
pre.back=c
lst.front=d
cut link: [a-b-c d-e]

We had to touch: pre.front pre.back lst.front c.next

[jonnin]

you have to touch each one to delete it anyway, is why I did that. the split logic looks like (roughly)

//loop to check # nodes in list > number deleted or not, if not delete all return empty
// else
//split list @ correct location
//touch each element removed to delete it in a loop** or not, see below
//return remainder as list

where this algorithm is useful, as I hinted at in the double posting other entry,
you can poke the deleted list intact into a node repository and use that instead of new to reuse the memory after 'deletion' -- deletion would just be pulling them off the list intact. Since you don't touch all the node to do that, its more efficient all the way around to do it that way (more efficient to reuse the memory, and more efficient to bulk 'delete'). This is significantly more complicated to implement, and your add-to-list becomes (if repository not empty, reuse a node, else new(node) ...) and weirdly your class now has another sub-list of the same type inside to hold the deleted stuff (really, a second head-pointer type entity). Your program can only grow in memory use, never shrink, using this, so if you allocate a million nodes, delete all but 10, you still have 1M memory held for re-use. And you have to truly delete it all at the program end of course.

[keskiverto]

jonnin wrote:

you have to touch each one to delete it anyway, is why I did that.

Yes, the initial question was about remove, but the later clarification shows that the goal is to move (up to) k elements from head into a new list. Hence, no delete.

[jonnin]

Sorry, I missed that.
in the case of splitting a list, you do want to do it in a chain. Does all of this make sense?