linked-list,lisp,cpu-cache , Are Lisp lists always implemented as linked lists under the hood?


Are Lisp lists always implemented as linked lists under the hood?

Question:

Tag: linked-list,lisp,cpu-cache

Are Lisp lists always implemented as linked lists under the hood?

Is this a problem as far as processor caching goes? If so, are there solutions that use more contiguous structures which help caching?


Answer:

Lisp implementations often can store some values directly in cons cells: fixnums, characters, ... For everything else a pointer will be stored in the car or cdr.

Nowadays almost all implementations which are using cons cells don't use optimizations like cdr-coding.

Memory locality usually is improved by using a copying / compacting / generational garbage collector.

Sometimes above GC stretegies are combined in fancy ways.

Also note that in many Lisp programs many of those cons cells may be short-lived:

(mapcar #'1+
        (mapcar #'isqrt '(10 20 30 40 50))  ; <- result is 'garbage'
        )

The list of integer square roots is immediately garbage. The function will just walk through the fresh cons cells and allocate new fresh cons cells and there won't be much cache non-locality.

Allocation of cons cells can be reduced by using destructive operations. Above can be written as:

CL-USER 24 > (let ((s (mapcar #'isqrt '(10 20 30 40 50))))
               (map-into s #'1+ s))
(4 5 6 7 8)

This will get rid of one allocated list and further improves locality.


Related:


Getting “symbols not found” errors implementing a Stack as Linked List using templates


c++,templates,linked-list,stack
I'm trying to create a stack using a linked list. I've already got it working using integers, but now I want to implement Templates to it. There are no errors detected before compile, but after running I get these errors: *Undefined symbols for architecture x86_84: "Stack::printStack()", referenced from: _main in...

Initializing a pointer to a struct with malloc [duplicate]


c,pointers,linked-list
This question already has an answer here: How do I modify a pointer that has been passed into a function in C? 5 answers This might be a question with a very simple solution but I can't get my head around it... I'm trying to implement linked list for...

I can't find the pointer error that's causing an intermittent crash. Can you?


c,pointers,linked-list
This works most of the time, but I get an occasional crash. There's a pointer problem somewhere but I can't see it yet. The code takes words out of a string, and builds a linked list of them. The words have to include adjacent punctuation, but no whitespace. For example,...

Deleting multiple nodes from simple linked list on C


c,list,linked-list,nodes,erase
I want to delete all nodes that have the same idteam as key, but it will crash... I know it should also free() the memory, but anyway I thought this should work :S //defining the struct struct players { int idplayer; int idteam; struct players *next; }; struct players *first,...

card game in c, shuffle linked list


c,linked-list,shuffle,realloc
I trying to shuffle a linked list in c. My idea was to move the list into an array of card then to shuffle the array and then to put it all back in the linked list. when I do build everything is ok but when id use the debugger...

threads safe linked list fine grained in C


c,multithreading,linked-list
I'm implementing a linked list with fine grained locking, meaning a lock in every node. When I'm adding a new node, I want to pass only 2 arguments: key and value. How can I make sure each node has a different lock? The lock is implemented by pthread_mutex_t. This is...

Common Lisp Object System method execution order


lisp,common-lisp,clos
I have the following two classes: (defclass person () ()) (defmethod speak ((s person) string) (format t "-A" string)) (defmethod speak :before ((s person) string) (print "Hello! ")) (defmethod speak :after ((s person) string) (print "Have a nice day!")) (defclass speaker (person) ()) (defmethod speak ((i speaker) string) (print "Bonjour!"))...

Deletion in Link List showing “0”


c++,linked-list
I cannot figure it out why am getting a 0 when trying to delete the first element of the list? I have inserted 3 elements (7,8,9),when am deleting 8 or 9 its working fine for me ,but when am trying to delete 7(.i.e the first element) irrespective of the no...

reverse a linked list using recursion error


c,recursion,linked-list
I am understanding recursion and so I tried writing reverse a linked list program. I have written the below function but it says segmentation error (core dumped). void reverse(){ if (head -> next == NULL){ return; } reverse (head -> next); struct node *q = (struct node*) malloc (sizeof(struct node));...

How to properly unit-test a linked list (using Python)?


python,unit-testing,linked-list
I'm new to TDD. I've created all the main functions (insert, search, remove etc.). This is my insert_beginning() function: def insert_beginning(self, node): ''' Inserts a Node to the beginning of the list. ''' node.set_next(self.head) self.head = node My question is, how do I properly unit-test this function? The only way...

Spliting Singly Linked List


c++,linked-list,singly-linked-list
I'm trying to split a singly linked list into 2 singly linked list. l1 will get 30% members of l and l2 will get the next 30% of l. I don't know what wrong with my code, so please help me. Thanks. P/s: Sorry for my bad English. #include <iostream>...

How to delete doubly linked list data and return it?


c++,data-structures,linked-list,doubly-linked-list
template <class T> class Node { public: T data; Node<T>* prev; Node<T>* next; // default constructor (parameterized) template <class T> Node(T value) { data = value; prev = NULL; next = NULL; } }; template <class T> T CircularLinkedList<T>::RemoveAt(int p){ Node<T>* temp = head; if (head == NULL){ return 0;...

C - Singly linked list - passing a pointer by value vs by reference


c,pointers,linked-list
typedef struct node { int data; struct node *next; } NODE; NODE* add_head(NODE **phead, int data) { NODE *new = (NODE *)malloc(sizeof(NODE)); new->data = data; new->next = *phead; *phead = new; return new; } NODE* add_tail(NODE **phead, int data) { NODE *p, *new = (NODE *)malloc(sizeof(NODE)); new->data = data; new->next...

Printing ith row jth column value in lisp


arrays,multidimensional-array,lisp,clisp
I am taking input N as number of rows of a 2D matrix in lisp, where each row can have maximum of 5 elements in it. So i make it like this. Now for eachrow as it can have any number of elements between 0 to 5. So I made...

Structuring large Lisp applications


lisp,common-lisp,quicklisp,asdf
I am currently trying to wrap my head around packages, systems & co. I now have read Packages, systems, modules, libraries - WTF? a few times, and I think I'm still having difficulties to get it right. If I simply want to split a Lisp source file into two files,...

How can I restart a double linked list?


c,linked-list
I'm coding a program to multiply two polynomials. I need some advice as to how I can restart the double linked list in the nested while loop in the polyProduct function. I mean, at this point I need to go back to the first position of the list. This is...

Bubble sort double linked list


c,sorting,linked-list,bubble-sort
Hello everyone I'm trying to sort my double linked list in C using bubble sort algorithm. Here is my code: struct node { unsigned char key; unsigned char num; struct node *left; struct node *right; }; Here is my sort funcion: void sort(int count, struct node *t_node) { struct node...

Backquote String Interpolation


macros,lisp,common-lisp
Is it possible to use lisp's macro to do string interpolation? For instance, can I make a macro like this: (defmacro test (a) `",a") So that (test abc) returns "abc" as a string? I could probably cheat by quoting it and turning that quote into a string, but that doesn't...

If strings are vectors, why are they immutable?


lisp,common-lisp
if strings are vectors of characters, and a vector's elements can be accessed using elt, and elt is setf-able - then why are strings immutable?

Exceed evaluation depth when forward function in Emacs Lisp


emacs,lisp,elisp
Here is just a simplified code snipped I have not managed to work. I do not understand what is wrong. (defun enumerate-indicies (func) (let ((index 0)) (while (< index 5) (funcall func index) (setq index (1+ index))))) (defun enumerate-multiplied-indicies (func) (enumerate-indicies #'(lambda (index) (funcall func (* 10 index))))) The following...

Big-O for 2 dimensional array and Linked list


c++,c,arrays,linked-list,big-o
I've made a game by using 9 linked Lists and the other 1 linked lists gets all the address of the other 9 linked lists. Therefore, something like a 2 dimensional array by using linked list. I'm trying to calculate Big-O that my data structure fits and is better than...

Linked list deletion and duplication


c++,c,linked-list
In the code I copied newnode to the headnode and also to the temp node. But when I delete an instance of data, it seems to affect the other locations as well. When I freed newnode it also erases the content of head and temp .How is this happening? Though...

<< Definition using inheritance and templates [duplicate]


c++,templates,visual-studio-2012,linked-list
This question already has an answer here: What is an undefined reference/unresolved external symbol error and how do I fix it? 18 answers I am trying to implement a Linked List in C++ using templates. Unfortunately I am getting an unresolved external error when I try to use a...

in clojure, function argument type mismatch


clojure,functional-programming,lisp
clojure, function argument is vector, but it takes a map without problem. (defn flower-colors [colors] (str "The flowers are " (:flower1 colors) " and " (:flower2 colors))) (flower-colors {:flower1 "red" :flower2 "blue"}) ;; -> "The flowers are red and blue" Function flower-colors suppose to take vector type argument, but with...

Error Queue implementation using Linked List


c++,data-structures,linked-list,queue
I am trying to impliment Queue using linked list but it goes stops unexpectidly. could not find why? #include <iostream> #include <string> using namespace std; Class Node for creating a node. class Node { public: int data; Node *next; }; Queue Class containing operations for Queue. class Queue{ private: Node*...

What is the idiomatic way to write a linked list with a tail pointer?


linked-list,rust,reference-counting
As a learning project for Rust, I have a very simple (working, if incomplete) implementation of a singly linked list. The declaration of the structs looks like this: type NodePtr<T> = Option<Box<Node<T>>>; struct Node<T> { data: T, next: NodePtr<T>, } pub struct LinkedList<T> { head: NodePtr<T>, } Implementing size and...

Linked list of pointers C++


c++,linked-list
I have a list but now I have to link it. Here is my program ( I deleted code inside functions to make my program more easy to read ). #include <iostream> using namespace std; struct Student { char ime[16]; char priimek[16]; char vpisna[10]; char ocenaRV[10]; char ocenaDN[10]; char ocenaKV[10];...

Removing a node from a LinkedList (C#)


c#,data-structures,linked-list,hashtable
I created a LinkedList class with a function delete to remove a certain node from the list if found, however it's not working: public class LinkedList { public Node head; <...> public void delete(string n) { Node x = search(n); //returns the node to delete or null if not found...

Is there a mistake in this illustration?


java,data-structures,linked-list,singly-linked-list
In chapter 14.2, page 620, in "Big Java" (International 4th edition), by Cay Horstmann, it is shown how to implement a linked list. The add method of the listIterator looks like this: public void add(Object element) { if(position == null) { addFirst(element); position = first; } else { Node newNode...

How to move a file in Lisp using rename-file


lisp,common-lisp,pathname
What's the best way to move a file in Lisp in an implementation-independent way? For example I have an image file: (setq oldpath #P"SERVER:PICTURES;TEMP;PHOTO.PNG") and I want to move it out of the TEMP directory into the PICTURES directory. This seems to work: (setq newpath (make-pathname :host (pathname-host oldpath) :directory...

Array of pointers to linked list


c,arrays,pointers,linked-list
I need to know if i want to make an array that every element of the array is a pointer to a linked list and pass the array to a function, the function is void because I need to change the array typedef struct n{ char *S; int num; }list;...

Find middle element of a double linked list in constant time complexity


linked-list
I am trying to find the middle element of a double linked list in constant time complexity . I came across the following http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ solution. But I don't understand how to use the middle pointer. Can anyone please help me understand this or give me a better solution .

Recursion of Linked List


java,recursion,nullpointerexception,linked-list
When given an array of integers, I'm trying to change each element with the product of the integers before it. For example, int[] array = {2,2,3,4}; is now: {2, 4, 12, 48}; I added each element to a LinkedList, and I'm trying to do this recursively. This is what I...

Value from binding in LFE interpreter using Erlang


erlang,lisp,lfe
I'd like to use Lisp Flavored Erlang as a scripting extension language for an Erlang application. If you want, in a similar way GNU Emacs is configured and extended via Emacs Lisp. I know that the argument is wide and structured; but in the specific case of this question I'd...

EVAL/APPLY: too many arguments given to F


lisp,common-lisp,clisp
Hello why do i get *** - EVAL/APPLY: too many arguments given to F on function call with nested lists parameter. I cannot figure it out, since I passed a simple nested list. (defun f (L) (cond ((NULL l) nil) ((listp (car L)) (append (F(car L))) (F(cdr L) (car (F...

Return items of a list in Lisp


lisp
I have to write a program in Lisp that returns the first item of a list if it contains an even number of elements, and the last if it contains an odd number of elements. I need a little advice on where to start? I don't need whole program.

Efficiently adding element to the top of the list


java,list,arraylist,enums,linked-list
I have an ENUM like this from which I always get what is my localFruit which can be either APPLE or ORANGE or BANANA. public enum Fruits { // it can have more elements here APPLE, ORANGE, BANANA; // some code } So let's say if APPLE is my localFruit,...

Insertion into a list doesn't reflect outside function whereas deletion does?


list,lisp,common-lisp
I am new to Lisp. Deletion of an item in a list by a function gets reflected outside the function but insertion doesn't. How can I do the same for insertion? For example (defun test (a b) (delete 1 a) (delete 5 b) (append '(5) b) (member '5 b)) (setq...

C++ Unable to Print Pointer Data of a Linked List


c++,linked-list,nodes
I'm dealing with a doubly Linked List. It's made up of classes and is centered around the current node (instead of a node in the beginning or end of the list). Now my print function will throw an error but only if I have traversed the list at all. My...

Why does ListIterator provide an index for elements in a LinkedList?


java,linked-list
Unlike an ArrayList, a LinkedList can not access an element at a particular point using an index. If this is the case, then what is the point of the ListIterator providing functionality that returns the index of a particular point in a LinkedList? Why would I ever need to know...

How to conditionally remove an element from a list using an iterator?


c++,linked-list,listiterator
Problem: I am writing a simple file manager application. In this program I have a "Directory" class: class Directory { public: Directory(string address, string directoryname) { this->path = address; this->name = directoryname; } string GetFullPath(){ return path == "/" ? path + name : path + "/" + name; }...

Mimic a LinkedList with a simple float[]


java,android,arrays,linked-list
I have to draw on a SurfaceView the trails of some object moving around. The trail of an object is implemented as a LinkedList of points (a point is a pair of float coordinates on the SurfaceView). The LinkedList is motivated by a behaviour like that public class Trail extends...

Recursion - nth element from last in a linkedlist


c,recursion,linked-list
Can someone please explain the following function ? void printNthFromLast(struct node* head, int n) { static int i = 0; if(head == NULL) return; printNthFromLast(head->next, n); if(++i == n) printf("%d", head->data); } I just want to know how order of execution of statements occur in recursion i.e given recursive call...

Using the runner technique for linked list


algorithm,linked-list
So, I am facing a doubt here. I was reading the book Cracking the coding Interview. The following text is written over there. Suppose you had a linked list a1->a2....->an->b1->b2....bn, and you want to rearrange it into a1->b1->a2->b2->.....an->bn. You don't know the length of the linked list but all you...

Why is my linked list only printing last entry?


c,file,linked-list
Im trying to read specific lines from a file and add it to a linked list and then print it out. Code bellow : #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct list { int uid; char* uname; struct list* next; }node; void push(node ** head, int uid ,char* uname)...

Issues with reversing the linkedlist


java,algorithm,linked-list,nodes
I'm trying to learn about linked list and it has been little challenging for me. I'm trying to reverse the link list with recursive method. Here is my code: public class ListNode { Node head = null; int nodeCount= 0; int counter = 0; ListNode(){ head = null; } public...

Invalid specialized parameter in method lambda list


lisp,common-lisp
I am trying to write a simple coin flip program in Common Lisp. This is the code I have (defun yn (let ht (random 1) (if (eq ht 1) (princ heads) (princ tails)) ) ) It seems simple enough, but I keep getting the error: "Invalid specialized parameter in method...

LinkedList Recursion


java,linked-list
public class LinkedList { Node head = null; int nodeCount= 0; int counter = 0; LinkedList() { head = null; } public Node reverseTest(Node L) { if(L == null || L.next ==null) { return L; } Node remainingNode = reverseTest(L.next); Node cur = remainingNode; while(cur.next !=null) { cur=cur.next; } L.next...

Linked List reversal in C not working


c,linked-list,singly-linked-list
I want to do some operations with linked list in C. I have wrote some functions for this like - Insert at beginning, Insert at tail, Delete from beginning etc. In my code I tried to implement reversal of linked list. But it is not working as expected. It always...

Return type of list front (C++)


c++,function,reference,linked-list,return-type
So I want to use a list for a part of my program. I'm trying to get acquainted to the library list, so I wrote a quick little program to help myself understand what's going on. It all works properly, but there's one thing I don't understand. According to this:...