The challenge: Implement a generic linked list that can contain typed values.
You may do either a black box array-like-interface, that provides index-based APIs, or a "white" box linked-list-style interface, that provides list-node-based APIs.
Variations: Implement both single and double linked versions. Feel free to copy and paste between them, but for exercise reasons, keep them separate, and do not try to reuse code.
Implement the four operations listed on the site:
- Get nth node or value, depending on white box or black box (the site calls it indexing, but that actually is only what one calls it for arrays)
- search for x value (which should return either the index, in the case of array-black-box interface, or a list node, if white-box linked list)
- insertion (which may be at-an-index in the case of black box, like typical arraylist insertion, or may be relative to a linked list node, in the case of white box)
- and deletion (which again, may take either an index or a list node depending on your api type)
Also implement these extra operations that are important but not listed on the site:
- append, without knowing how much is in the list, might be O(n) or O(1) depending on things
- iterate (good for testing)
- length - should be O(1) to get
Optionally, your can get bonus points for:
- implementing both an indexing-based black box api and a list node-based white box api that can be used on the same list
- if you do white box, providing a "get index given a list node" operation - May be O(n)
If you have to make a trade-off, pick the mentally simpler thing, generally. there are a couple of tradeoffs where it seems like it could be better than naive, but the naive thing is fine.
as usual, write whatever tests you need to to verify that it works.
note to anyone who finds this on my gist page: this was reformatted from chat. sorry for bad grammar.