class List
attr_reader :car, :cdr, :size
def initialize(*args)
if args.size.zero? then
@car = nil; @cdr = nil; @size = 0
elsif args.size == 1
@car = args[0]; @cdr = List.new; @size = 1
else
@car = args[0]
@cdr = List.new *args[1 .. args.size - 1]
@size = args.size
end
end
def [](n)
raise ArgumentError unless n.class == Fixnum
unless n > @size - 1 then
if n.zero? then @car
else @cdr[n - 1] end
end
end
def []=(n,a)
raise ArgumentError unless n.class == Fixnum
unless n > @size - 1 then
if n.zero? then @car = a
else @cdr[n-1] = a end
else raise ArgumentError
end
end
def length
@size
end
def null?
@cdr.nil?
end
def member?(a)
if a.nil? then true end
unless self.null? then
if @car == a then true
else @cdr.member? a end
else false
end
end
def include?(a)
self.member? a
end
end
Name:
Anonymous2012-02-04 19:25
>>40
>yeah, but people often uses lists when ordering is not an issue
Linked lists *preserves the order*. If you aren't concerned about order, then you would use something like a bag. In which case some of the latter operations will run faster.
Lists are awesome when merging sorted collections in some way
This isn't true for certain types of linked lists in C.
Name:
Anonymous2012-02-04 20:19
>>41 >>42
And this basic argument, in the context of C/C++/Java, can be applied to lists in general.
Name:
Anonymous2012-02-04 20:46
Change out old element with NULL (or some invalid value), then re-order only when you run out of space and have to re-allocate, so it's amortized O(1).
example? I'm sure if it could exist in C, it could exist elsewhere as well.
Although, come to think of it, you can merge sorted arrays just as easily as linked list, but with linked list, you can do more in place modifications, whereas with arrays you have to copy content out to a third array. Although that isn't that big of a deal if you can reuse arrays.
>>44
You sound like frozen void. Do you make your arrays 2000000.... in size as well?
Name:
Anonymous2012-02-04 22:51
Someone say O(1) remove for an array?
class Array
def remove(n)
# Example implementation. Real implementation will have certain exemptions
# Such as a case where n == 0 or such. I'm just being lazy here.
self[0..n-1] + self[n+1 .. size-1]
end
end
Name:
Anonymous2012-02-04 22:53
>>48 amortized order 1 time isn't always acceptable.
Then certainly the immense overhead of linked structures aren't acceptable either.
Do you make your arrays 2000000.... in size as well?
No you fucking retard.
Name:
Anonymous2012-02-04 23:05
>>51 Then certainly the immense overhead of linked structures aren't acceptable either.
A JIT compiler can replace immutable linked lists with mutable arrays where appropriate.
Name:
Anonymous2012-02-04 23:08
>>44
Set approach is better and you don't deal with random NULLs in the middle of the array where one isn't expected.
Name:
Anonymous2012-02-04 23:11
IF YOU WOULD ALL JUST USE x86 ASM BY INTEL THEN YOU WOULDN'T HAVE THESE PROBLEMS FUCKING PEASANTS
x86 SUPREMACY
Name:
Anonymous2012-02-04 23:19
>>52
So you agree that arrays are superior to linked structures, and that any issue with arrays may be fixed by just adding more arrays?
Name:
Anonymous2012-02-04 23:19
>>54
x86 asm is there so you can write high level things on top of it, not for direct use, you mental midget
tell that to everyone in the 80s
tell that to all the embedded designers
Name:
Anonymous2012-02-04 23:23
>>58 Consider the following: Imagine if DRAM was a linked-listed
Consider imagining that DRAM was a linked-listed? I want whatever you're having.
Name:
Anonymous2012-02-04 23:24
>>59
We're no longer in the 80s, and I don't think anyone sane uses x86 for embedded designs.
Name:
Anonymous2012-02-04 23:27
x86 and other assembly languages are directly useful for things like encryption, specifically when vector intrinsics just don't cut it.
Name:
Anonymous2012-02-04 23:28
>>61
Any sane embedded designer that wants a good fast product would be using [insert_instruction_set_here] to get the job done correctly and efficiently.
Name:
Anonymous2012-02-04 23:42
>>63
For mobile bullshit devices (I fucking hate smartphones), x86 is too power-hungry and won't work. For little CPUs embedded in industrial machinery, going full retard with a complex Intel CPU is stupid while you could do the same thing with some little microcontroller with 128K of embedded DRAM. Face it, x86 is made for desktops and (to some extent) laptops.
Name:
Anonymous2012-02-04 23:49
>>64
Are you retarded? I said [insert_instruction_set_here] for a god damn reason you fuck, of course i realize x86 isn't used in most of those products.
>>51
The overhead of providing links is not that large if the size of the objects is much larger than a pointer, or two pointers. You'll be using a lot of extra memory if you try to do a linked list of characters though, and if you tried to store 500MB of characters in a linked list. But maybe that could be useful for some type of splicing algorithm. It kind of reminds me of DNA or something.
But there are times where it is important every operation must finish below a certain amount of time, even if it makes each operation slower. Being really fast for a while, and then suddenly taking time proportional to the number of prior operations could be bad when you need to keep things in synch, like a media player or something.
Name:
Anonymous2012-02-05 0:04
>>68
I'm not talking about memory overhead, although it's kind of linked with what I'm saying (don't mind the pun). Linked structures are just inherently cache inefficient, arrays do things much faster on modern architectures.
>>69
No, linked structures are not inherently cache inefficient. There's nothing that says that linked structures somehow can't be close in memory.
Copying garbage collectors routinely move objects that refer to each other into a common shared region. Some fancy LISP collectors in the old and days of you're even removed the cdr pointer with the following pair itself (and so on).
In C you can easily put your list nodes in an array and allocate them from there. If the nodes get too spread out, move the nodes to one end (in sorted order).