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.