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
C++ DOES have a default version of linked lists though, and C++ is pretty much C but better. Also, your C doubly linked list cannot store data, just other lists.
>>10
So basically if you want to simulate lisp lists you only make a pair class like so:
class Cons
attr_accessor :car, :cdr
def initialize(car, cdr = nil)
@car, @cdr = car, cdr
end
end
def list(*values)
node = start = Cons.new(values.shift)
for value in values
next_node = Cons.new(value)
node.cdr = next_node
node = next_node
end
return start
end
Yes, but I wanted to add a little bit of Ruby touch by giving it more than the standard "just car and cdr" crap. Any element in my lists can give you the value at any index like an array (but still in O(n), sadly)
Name:
Anonymous2012-02-04 14:26
>>15 (cdr (list 1 2 3))
This works like the list function in >>14. There's no list datatype involved. It just chains together pairs and then returns the first pair.
more than the standard "just car and cdr" crap
You can extend >>14 just like in lisp by writing functions that operate on the structure returned by the list function.
Of course the clean way to do it in ruby is defining a list class but then you hide the implementation and use names like head and tail that actually make sense for a list.
I'm in no way saying that's the best implementation of a doubly linked list for C or that it even closely resembles that of a Con cell. How about you go back to the local bar and drown away your sorrows faggot.
Name:
Anonymous2012-02-04 15:04
Linked
Linked is shit, array based is always better.
>>24
Except that you can easily make an O(1) implementation, just because you're a stupid piece of shit doesn't mean that everybody else are too.
Name:
Anonymous2012-02-04 15:11
#include <stdio.h>
int car(int *arr){
return *arr;
}
int *cdr(int *arr){
return arr+sizeof(int);
}
int main(void){
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
int i;
for(i=0;i<10;++i){
printf("%d ",car(arr));
arr = cdr(arr);
}
}
Am i doin it rite? Java programmer here
Name:
Anonymous2012-02-04 15:12
>>18
I mean you expose the interface of a list, not the interface of a pair. Something like this:
class List
def initialize(*values)
if values.empty?
@list = nil
return
end
last_node = Cons.new(values.pop)
@list = values.reverse.inject(last_node) {|l,v| Cons.new(v,l)}
end
class Cons
attr_accessor :car, :cdr
def initialize(car = nil, cdr = nil)
@car, @cdr = car, cdr
end
end
def head
@list.car
end
def tail
es = []
e = @list.cdr
while e
es << e.car
e = e.cdr
end
List.new(*es)
end
def length
e = @list
l = 0
while e
l += 1
e = e.cdr
end
return l
end
end
I like this. It's great for immutable lists, but it doesn't support the cons operation so well. So some other list interface would be needed to make efficient use of it.
Oh! an array with O(1) of every kind of operation to go along with its O(1) access. Perhaps its search is also O(1), it is concurrency safe, has a 2 foot penis, gets all the bitches, and maxes out scores at donkey kong arcades.
Name:
Anonymous2012-02-04 15:34
>>26
Show me an O(1) remove operation for a array that doesn't just sub in NULL.
Name:
Anonymous2012-02-04 15:40
>>29
I don't know the exact definition of a Cons operation but is it something like:
int *cons(int *arr,int n){
int *narr = malloc(sizeof(int)*(sizeof(arr)/sizeof(int))+1);
int i;
narr[0] = n;
for(i=0;i<(sizeof(arr)/sizeof(int));++i)
narr[i+1] = arr[i];
return narr;
}
Assuming this only works for ints, did i do that write or did i get it completely wrong?
No, you do it. Hint: one method involves giving up maintaining the order of the elements in the array, which is perfectly acceptable when you are just representing a set, and the ordering is not important within the set. If the size of the elements are small, around the size of a pointer, then this will save more memory than a doubly linked list, although reallocating the array can cause stalls. But this can be avoided if you can anticipate in advance a reasonable upper bound for the amount of elements in the set.
>>36
You replace the element removed with the last element in the list. The place where the last element used to be becomes NULL.
As the other guy said this only will work out as long as you don't care about order in your list.
>>34
That makes it a set, not a list. What you're saying is essentially "ordered linked lists suck, unordered array-based lists are better."
Name:
Anonymous2012-02-04 18:18
>>31 Show me an O(1) remove operation for a array that doesn't just sub in NULL.
So basically you're asking him to show you an O(1) remove for an array that can't be an O(1) remove for an array?
yeah, but people often uses lists when ordering is not an issue. Lists are awesome when merging sorted collections in some way. If you need it sorted, and you need to search for random keys, and you need to support random deletion and insertion, then balanced ordered trees are better. If you need it sorted, and will be accessing random keys, but never inserting or removing, then a sorted array with binary search is pretty good, compact, and fast. If you can drop the sorted requirement, then hash tables are nice.
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).