3 Replies - 904 Views - Last Post: 31 October 2013 - 10:22 AM

#1 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,303
  • Joined: 11-December 07

Linked List: Interface or cons cells

Posted 29 October 2013 - 05:16 PM

I was having a discussion with a colleague that I thought would be interesting to bring up here. It was about how linked lists should be implemented.

We all know that a linked list consists of linked nodes. Each node contains a value and a link to another node. It is terminated with a null or an empty list depending on the language.

Functional languages augment this by providing a bunch of functions that process lists but they also expose the nodes which gives a lot of flexibility and power to the programmer.

Object orientated languages hide the workings of the list and expose list operations through an interface. This has the advantage that different list implementations can be substituted with no change to the code.

I learned OO programming first so the interface approach seemed most natural to me. My colleague learned functional programming first and he thought that the node structure should be exposed in OO languages as in functional languages. At the time, I thought he has just missed an important aspect of OO programming but since then there have been times when I wished I could deal with data structures like I can in functional languages.

What do you think? There must be more depth to this than we thought of.

Is This A Good Question/Topic? 0
  • +

Replies To: Linked List: Interface or cons cells

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: Linked List: Interface or cons cells

Posted 29 October 2013 - 08:02 PM

View Postcfoley, on 29 October 2013 - 08:16 PM, said:

At the time, I thought he has just missed an important aspect of OO programming but since then there have been times when I wished I could deal with data structures like I can in functional languages.


You mean like the situation where a strand of DNA is stored as List<Base> and you want to splice another strand, it would be nice to just sent the next pointer instead of having to add/remove items from the list?

For me, this is when I realize that I shouldn't have used the stock List<Base> but instead should have used LinkedList<Base>. Why? To me if I was using the List<T>, the information I want to communicate to the readers of my code is that I just was to store my bases in a container that encapsulates the behavior of a list, but by choosing LinkedList<T>, I'm communicating that not only do I want to store my bases in a container the behaves like a list, but additionally, I want to have access to the nodes of that list. Of course, I'm still hosed because I believe that C# LinkedList<T> still doesn't let me manipulate the Next pointer. I'll have to roll my own.
Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2068
  • View blog
  • Posts: 4,303
  • Joined: 11-December 07

Re: Linked List: Interface or cons cells

Posted 31 October 2013 - 08:02 AM

Yes, that's a good point. It's the encapsulation, not just the interface. I guess it's pretty easy to roll your own.
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5909
  • View blog
  • Posts: 12,815
  • Joined: 16-October 07

Re: Linked List: Interface or cons cells

Posted 31 October 2013 - 10:22 AM

Simply, functional cons lists should be immutable. If this is the case, then expose away. Of course, all you're exposing is a struct with an immutable value and pointer. You want the same style in an OO language, you can easily make both those values read only and have at.

In a functional language, you'll often consider the cost of asking for the length of a list or how it's immutable nature allows neat reuse or requires copying. In OO, the programmer only need worry about the interface; it's up of the implementer to make it as efficient as possible.

It's more a question of style than anything else. I can't say that either approach is better. They've both risen to prominence in their respective ecosystems for a reason.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1