www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4420] New: insertBack() for SList

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420

           Summary: insertBack() for SList
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: jmdavisProg gmail.com



22:57:31 PDT ---
SList has an insertFront() but not an insertBack(). I assume that this is
because SList is a singly linked list and the last element does not have a link
to the element before it (in fact, looking at the implementation, you don't
even keep track of the last element).

However, if you keep track of just a bit more than the head node, you can
implement insertBack() as well better optimize some of its functions (like
findLastNode()). If you kept track of the last node in addition to the first
one, then you have the last node for functions like findLastNode() and you can
have back() and insertBack(). For that matter, if you made it the last two
nodes, then you could have popBack() as well. Now, that may complicate the
other list operations too much to be worthwhile, but it would expand SList's
capabilities without unduly increasing how much memory it takes like you would
with a doubly linked list.

So, it may be a bad idea when you really get down to it, but I thought that I
should at least suggest it since it would make SList more versatile.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 03 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420


Jonathan M Davis <jmdavisProg gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 03 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei metalanguage.com



02:01:26 PDT ---
SList can't implement insertBack due to complexity requirements. To append to a
list, use lst.insertAfter(lst[], stuff).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420




02:40:40 PDT ---
Which complexity requirements? I understand that it can't do it as is because
that would be O(n). I was pointing out that it kept track of the last element
in addition to the first one, it could implement insertBack() in O(1) without
needing the extra space per node that a doubly linked list requires. And if it
keeps track of the next-to-last node as well, then it can implement popBack()
in O(1) as well. Is it that other operations no longer fit the appropriate
complexity requirements if it keeps track of the last element in addition to
the first? I would think that the other operations would have the same
complexity but with (in some cases) a slightly higher constant - as in xO(1)
would have a greater value of x rather than becoming O(n) or O(log n) or
anything worse than O(1).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420


Simen Kjaeraas <simen.kjaras gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |simen.kjaras gmail.com



PDT ---


 And if it keeps track of the next-to-last node as well, then it can implement
 popBack() in O(1) as well.


How could it? It could popBack once, then you'd need to recalculate
next-to-last.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420




03:38:29 PDT ---
Ah. Good point. I obviously didn't think that one through thoroughly enough.
You could popBack() once, but that would be it. Scratch that idea.

However, you could still have insertBack() and back() if you kept track of the
last element. back() would return that last element and insertBack() would
insert after it, adjusting the last element's pointer to its next element to
point to the new last element and adjusting the container's pointer to the last
element to point to the new last element. So, that should work in O(1), but no
popBack() wouldn't work.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX



12:42:42 PDT ---
The main selling point of SList is simplicity. Adding all sorts of storage
aides is possible but would work against SList's charter. Feel free to propose
a new type based on SList in an enhancement proposal.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4420




16:44:47 PDT ---
Well, like I said, the addition might not be worthwhile. It would complicate
some of the other functions somewhat. It's just that it would be a fairly
simple addition to get some extra functionality in comparison to say, a
doubly-linked list. I have no problem if you don't think that it's appropriate
to add that extra functionality to SList. I just thought that I'd point it out
in case such a change would be desirable and the idea hadn't occurred to you.

Personally, in my code, I'd generally just as soon use a doubly-linked list in
most cases if I'm going to use a list. But SList as-is definitely has its uses,
and a doubly-linked list is overkill for some situations. It probably isn't
worth creating a separate SList class with just the additions to support back()
and insertBack() though.

In any case, this was just a suggestion, and if you don't want to use it,
that's fine by me.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 04 2010