3 ms·

> For example, a loop which appends to the end of a linked list is a bad idea, since finding the end of the list requires looping through all the nodes. This is

by douche 10y ago

> For example, a loop which appends to the end of a linked list is a bad idea, since finding the end of the list requires looping through all the nodes. This is a loop inside a loop (AKA O(n^2)) when we intuitively know that only a single loop is required (AKA O(n)). That would be indicative of a bad/naive linked-list implementation, wouldn't it? It's not that much overhead to maintain a wrapper with front and back pointers.

chriswarbo 10y ago
Well, there are some caveats. Firstly, that would technically be a double-ended queue ("dequeue") rather than a linked list. That's fine if you're using it as an abstract datatype, i.e. you're doing things like "myList.append(foo)", "myList.get(0)", etc. and hence you're able to swap out the implementation of those methods. There are some widespread cases of these naive datastructures which don't fit that model though. For example, Lisp makes heavy use of "cons" to pair up two values. By nesting these pairs, we can get arbitrary tree structures, and this is how lists are implemented, e.g. "(list 1 2 3 4)" is equivalent to "(cons 1 (cons 2 (cons 3 (cons 4 nil))))". These structures are heavily used in Lisp (since it does so much "LISt Processing"), and since the language is so dynamic it's hard to compile it away. Haskell's default list type works in this way too. There, the problem is compounded by immutability: changing the start of a list is easy, since we can re-use the pointer (immutability allows a lot of sharing). For example, if "list1" is "[1, 2, 3]" and "list2" is [9, 2, 3]", they can share the "[2, 3]" part: 1 ^ | list1: cons * *----+ 2 3 | ^ ^ V | | cons * *--->cons * *--->nil ^ | list2: cons * *----+ | V 9 However, if "list3" is "[1, 2, 5]", it can't share any of the "list1" or "list2" structure: the last element is different from the other lists, which requires the second-to-last element to use a different pointer, which makes it different from the other lists (even though it uses the same element); this requires a different pointer in the third-to-last element, and so on: 5 ^ | list3: cons * *--->cons * *--->cons * *----+ | | | V | | 1 | | ^ | | | V | list1: cons * *----+ 2 3 | | ^ ^ | V | | V cons * *--->cons * *--->nil ^ | list2: cons * *----+ | V 9 The problem's not as bad in Haskell as it is for Lisp: Haskell doesn't allow as much dynamic behaviour, so a lot more usage information is available during compile time, and allows optimisation like "list fusion". Also, Haskell makes it easy for programmers to define their own datatypes (like dequeues), and allows datatypes to be abstract (either using typeclasses or "smart constructors"). Being abstract makes pattern matching more difficult though (requiring "views").
- douche 10y ago
  Ah, I was thinking more in terms of C/C++/Java/C# style linked lists, which tend to look something like this: class List<T> { ListNode<T> head; ListNode<T> end; int size; } class ListNode<T> { T data; ListNode<T> next; // possibly, if it is doubly-linked ListNode<T> prev; }

by douche 10y ago

chriswarbo 10y ago

Well, there are some caveats. Firstly, that would technically be a double-ended queue ("dequeue") rather than a linked list. That's fine if you're using it as an abstract datatype, i.e. you're doing things like "myList.append(foo)", "myList.get(0)", etc. and hence you're able to swap out the implementation of those methods. There are some widespread cases of these naive datastructures which don't fit that model though. For example, Lisp makes heavy use of "cons" to pair up two values. By nesting these pairs, we can get arbitrary tree structures, and this is how lists are implemented, e.g. "(list 1 2 3 4)" is equivalent to "(cons 1 (cons 2 (cons 3 (cons 4 nil))))". These structures are heavily used in Lisp (since it does so much "LISt Processing"), and since the language is so dynamic it's hard to compile it away. Haskell's default list type works in this way too. There, the problem is compounded by immutability: changing the start of a list is easy, since we can re-use the pointer (immutability allows a lot of sharing). For example, if "list1" is "[1, 2, 3]" and "list2" is [9, 2, 3]", they can share the "[2, 3]" part: 1 ^ | list1: cons * *----+ 2 3 | ^ ^ V | | cons * *--->cons * *--->nil ^ | list2: cons * *----+ | V 9 However, if "list3" is "[1, 2, 5]", it can't share any of the "list1" or "list2" structure: the last element is different from the other lists, which requires the second-to-last element to use a different pointer, which makes it different from the other lists (even though it uses the same element); this requires a different pointer in the third-to-last element, and so on: 5 ^ | list3: cons * *--->cons * *--->cons * *----+ | | | V | | 1 | | ^ | | | V | list1: cons * *----+ 2 3 | | ^ ^ | V | | V cons * *--->cons * *--->nil ^ | list2: cons * *----+ | V 9 The problem's not as bad in Haskell as it is for Lisp: Haskell doesn't allow as much dynamic behaviour, so a lot more usage information is available during compile time, and allows optimisation like "list fusion". Also, Haskell makes it easy for programmers to define their own datatypes (like dequeues), and allows datatypes to be abstract (either using typeclasses or "smart constructors"). Being abstract makes pattern matching more difficult though (requiring "views").

douche 10y ago
Ah, I was thinking more in terms of C/C++/Java/C# style linked lists, which tend to look something like this: class List<T> { ListNode<T> head; ListNode<T> end; int size; } class ListNode<T> { T data; ListNode<T> next; // possibly, if it is doubly-linked ListNode<T> prev; }