QUICK! Implement linked list in language of your choice. If

{val: null, next: null}

LinkedList<T> linkedList = new LinkedList<T>()

>>60217433

var linkedList = require("linked-list");

and people say writing efficient code in java script is impossible. LOL

>>60217433

python 3:

linked_list = {0: ('a', 1),
               1: ('b', 2),
               2: ('c', 3),
               3: None}

def reverse(in_linked_list):

        # find list item
        for key, val in in_linked_list:
            if val is None:
                next_key = key-1

        # walk through the list backwards and print the value
        while next_key >= 0:
            print(in_linked_list[next_key][0])
            next_key -= 1

        return 'haha benis :DD'.

i decided to do the challenge without any googling or testing so i have no idea if it works

>>60218222

fuckin lol

Ouch, it was tricky.

Fixpoint mlist (T : Type) (n : nat) : Type :=
  match n with
  | O => forall U : Type, U -> U
  | S n => forall U : Type, (T -> mlist T n -> U) -> U
  end.

Definition empty : forall T : Type , mlist T 0 :=
  fun _ _ empty => empty.

Definition cons :
  forall (T : Type) (n : nat), T -> mlist T n -> mlist T (S n) :=
  fun _ _ hd tl _ node => node hd tl.

Axiom unit : Type.
Axiom IO : Type -> Type.
Axiom nop : IO unit.
Axiom seq : IO unit -> IO unit -> IO unit.

Fixpoint rev_print
  (T : Type) (n : nat) (print : T -> IO unit)
  (l : mlist T n) : IO unit :=
  let f :=
    match n return mlist T n -> IO unit with
    | O => fun l => l (IO unit) nop
    | S n =>
      fun l =>
      let node (hd : T) (tl : mlist T n) : IO unit :=
        seq
          (rev_print T n print tl)
          (print hd) in
      l (IO unit) node
    end in
  f l.

File: spurdo_face.png (13KB, 528x404px) Image search: [Google]

13KB, 528x404px

>>60218252

im bajeet in training :DD

if it's that bad how would you do it

What's a linked list?

>>60218329

It's in the OP.

Double or singly linked?

>>60217433

struct linkedlist_node {
    int val;
    struct linkedlist_node *next;
};

void linkedlist_reverse_print(struct linkedlist_node *start)
{
    struct linkedlist_node *nextnode = start->next;
    if(nextnode != NULL) {
        linkedlist_reverse_print(nextnode);
    }
    printf("%d ", start->val);
}

>>60218329
Pretty much an array, but you can arrange the values as you see fit by changing what value the pointer points to.

>Error: Our system thinks your post is spam.
welp

it was a good one too

File: 1493107652291.jpg (67KB, 1024x768px) Image search: [Google]

67KB, 1024x768px

>>60218222

File: catwince.jpg (2KB, 125x125px) Image search: [Google]

2KB, 125x125px

>>60218532

i tried

>>60217433

(reverse list)

>>60218291
Is this the lang that proves that it works.

>>60218617
It's coq.

>>60218295

class LinkedList(object):
    def __init__(self, data):
        self.next = None
        self.data = data
    def reverse(self):
        if self.next is not None:
            self.next.reverse()
            self.next.next = self
        self.next = None

>>60218295

Using Python for this task is just a bad idea. Python has lists, so use lists. Besides that you're supposed to link them, not just stuff them all in a dict.

>>60218373
>Not using typedef
>using recursive function to iterate the list
>at least you picked a real language
Let's hope you are a freshman and not a bajeet

File: leonard.jpg (24KB, 515x375px) Image search: [Google]

24KB, 515x375px

>>60218680

oh i see

i thought a class would have been overkill but i guess not

i only got into coding during my last year of uni and am otherwise totally self-taught by whatever i can automate at work

i wish so bad that i could turn back the clock and do software eng instead so i could get a really good grasp of the fundamentals like this. i realized too late that i really enjoy programming

thanks

>>60218634
You're a coq.

>>60218724
Also where is poop init() and insert ?

>>60218222
Storing nodes in a Hashmap is actually a pretty clever solution. Don't listen to the other guys here.

>>60218772

im the (You) in this post

looking back at it i can see problems with insertion, tuples are immutable so you would have to redefine every subsequent value in the dictionary every time you want to insert (or delete)

the biggest mistake i made was not using a class. i thought it would be overkill but every solution i see on the internet uses a linkedlist_node class

>>60218772
It's not clever at all. The indices are 0..n, it may as well be a list

>>60218826

and we come full circle

>>60217433
(list 1 2 3 4)

>>60218826
...until you want to delete and insert nodes in the middle. After just a few insertions and deletions, hashmaps will be much better algorithmically.

Also, in statically typed languages with value types, nodes stored in a Hashmap would allocate and deallocate much more efficiently, since you effectively have a pool allocation pattern. Allocating a general instance of a class is more expensive.

File: The+cycle+of+internet+content+read+desc+hello+funnyjunk+i_f72386_3447414.jpg (24KB, 457x594px) Image search: [Google]

24KB, 457x594px

>>60217433
Pictorial form.

>>60218680
>100000 element list
>Run this
>Computer now on fire

What did I do wrong?

>>60219052
You used linked lists for anything more than a trivial homework assignment.

https://youtu.be/YQs6IC-vgmo

>>60219052
Your reverse method is a mess. I suggest rewriting it with a for loop and no recursion because Python is shit and doesn't have TCO. Pop nodes off the front of one list and use that to build another.

>>60217433

data List a = Empty | Entry a (List a)

reverseOfList Empty = Empty
reverseOfList (Entry x xs) = (reverseOfList xs) concat x

Obviously you need to implement concat

>>60219163
>TCO
Lol

Dumb fucker

Write a reverse function that is capable of being optimized with TCO

>>60219146
It's called irony, retard. I know lists are usually bad.

>>60219164
You can do this more efficiently. Your reverse is O(n^2) because concat is O(n) for immutable lists. Reversing a list/stack can be done in O(n).

>>60219213
Haskell example:

data List a = End | Node a (List a)

reverse x = worker x End
    where
        worker End ys = ys
        worker (Node x xs) ys = worker xs (Node x ys)

>>60219322
Nope, not TCO optimizable

>>60219519
Are you retarded or something?

>>60218291
Coq has lists in the standard library

Inductive list (A : Type) : Type :=
 | nil : list A
 | cons : A -> list A -> list A.

>>60218329
The important thing is that you don't declare the list's size in advance. You add items to the list as you need to.

At least that's how it was, back in the day before the day. Maybe things have changed.

>>60217433
>Implying leaving /g/ is a bad thing

>>60217433
No. Linked lists are inefficient and I refuse to use them unless you can tell me exactly why you want them. I take pride in my code being efficient.

std::list<int> niceList;

for(auto it = niceList.rbegin(); it != niceList.rend(); ++it)
        std::cout << *it << std::endl;

>>60219146
While this is true, his reasons for it are mostly retarded. His argument is that the linear search for the element you want to remove dominates the time taken by the algorithm, but in reality the whole point of linked lists is that you never have to do that linear search. You always save a direct pointer to the cell in the list so that you can unlink it directly, or even let the links be part of your main data structure itself.

The real reason why linked lists suck is that iterating through them thrashes your caches, and that loading one element during iteration is data-dependent on having loaded the prior element.

>>60219858
>I take pride in my code being efficient
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. Good luck.

Elixir:

[1,2,3]

Lists are implemented as linked lists xd

>>60219980
If I could do that efficiently I would be quite rich indeed

>>60218222

list = [3, [4, [5, [6, []]]]]
def reverse(ls):
    ret = []
    while ls:
        ret = [ls[0], ret]
        ls = ls[1]
    return ret

>>60218724
>using typedefs for simple things and making a big deal about it

You are straight from a pajeet training course.

>>60220009
Just because there is no magic maths trick to find it doesn't mean it can't be done as efficiently as possible. I can find and prove the sum through a bound of 100,000 in under 50 seconds in pure Python. It requires 47,106,418 iterations through 5 nested loops to do so, excluding primes 2 and 5. At this scale, even unnecessary function calls slow the code down.

>>60218724
>>using recursive function to iterate the list
What would be the better method? I thought this was rather clever DESU

struct Node { 
  int val; 
  struct Node *next; 
}; 

void
print_list(struct Node *list)
{
  struct Node *node = list;
  
  for(; node != NULL; node = node->next) 
    printf("%d", node->val); 
   
} 

you can't make a linked list in x86 assembly

File: tmp_15139-1490100497508-390903704.png (775KB, 895x905px) Image search: [Google]

775KB, 895x905px

>>60220533
Yes you can faggot

>>60220424
Shouldn't it be:

 for(; node !=NULL; *node = node->next) 

And more importantly, that for loop doesn't print the numbers backwards.

Disclaimer: I took C++ many, many years ago. Prove me wrong, faggot.

>>60220589
WRONG

>>60220295
Reverse in place by setting cur node ptr to previous node iteratively and then printing it by iterating again, or at least pass Val to the recursive call so that it can be made into a tail call.

>>60220616
node is a pointer to a Node, node->next is a pointer to a Node. *node = node->next would be trying to assign a Node pointer to a Node. It is correct to do node = node->next which is making node point to node->next

>>60217433

(define my-list (list 1 2 3 4 5))
(reverse my-list)

>>60217433

struct LinkedList 
{
        LinkList nextVal;
        object Value;
}

struct Node {
    void *car, *cons;
};

void reverse(Node **head) {
    Node *prev, *next;
    while (*head != NULL) {
        next = (Node *) (*head)->car;
        (*head)->car = prev;
        prev = *head;
        *head = next;
    }
    *head = prev;
}

void print(Node *head) {
    while (head != NULL) {
        printf((char *) head->cons);
        head = (Node *) head->car;
    }
}

Can't test that it's correct but I reckon it should work

>>60217844
Came here to post this, glad someone already did it.
Every other response is shit.

#include <iostream>
#include <string>
using namespace std;
typedef string Node;

Node createNode(int val) {
        cout << "created Node with val" <<  val << "\n";
        return to_string(val);
}

void linkNode(Node node) {
        cout << "added node" << node <<  "to list\n";
}

void revList() {
        cout << "6 - 5 - 4 - 3\n";
}

int main() {
        Node n1 = createNode(3);
        Node n2 = createNode(4);
        Node n3 = createNode(5);
        Node n4 = createNode(6);
        linkNode(n1);
        linkNode(n2);
        linkNode(n3);
        linkNode(n4);
        revList();
        return 0;
}

File: suiguetsu'd again.jpg (81KB, 677x1082px) Image search: [Google]

81KB, 677x1082px

>>60222281
Sorry, correct me if I'm wrong:

Your program does the following:

 
   1) turns the keyword(?) string into node
   2) prints several statements
        a) of which, the value is NULL
        b) and then said NULL value is changed to a string type (same thing)
        c) then stored in the alt keyword for string n*
   3) Then you pass NULL to  string node and write a sentence
        a) You need spaces between the 'e' and ' " ' else  you'd get "added nodeNULLto list"
        b)  :^)
   4) then you say ""6 - 5 - 4 - 3\n" for some reason

>>60222526
wait whoops I'm wrong. You pass along values in the createNode... XD

so NULL should be <number>

C#

    class Node<T> {
        public T obj;
        public Node<T> next;
        
        public Node(T t) { obj = t; next = null; }
    }
    
    class LinkedList<T> {
        private Node<T> list;
        private Node<T> front;
        
        public LinkedList() { list = front = null; }
        
        public void add(T t) {
            if (list == null) {
                list = new Node<T>(t);
                front = list;
            } else {
                front.next = new Node<T>(t);
                front = front.next;
            }
        }
        
        public void reversePrint() { var temp = list; reversePrint(temp); }
        
        private void reversePrint(Node<T> node) {
            if (node != null) {
                reversePrint(node.next);
                Console.WriteLine(node.obj);
            }
        }
    }

>>60223053

public void reversePrint() { reversePrint(temp); }

Woops fixed

<!DOCTYPE html>
<html>
<body>

<script>

function linkedList(previousLinkedList, value) {
   this.previousLinkedList = previousLinkedList;
   this.value = value;
   return this;
}

function printReverseOrder(linkedListLastElement){

  var e = linkedListLastElement;
  
  for(;;){
    document.write(e.value + '<br/>');
    e = e.previousLinkedList;
    if(!e){
      break;
    }
  }
}

var previousLinkedList = null;

for(var i = 0; i < 10; i++){
  previousLinkedList = new linkedList(previousLinkedList, i);
}

printReverseOrder(previousLinkedList);

</script>

</body>
</html>