-1

I have been doing some practice problems on LinkedList but more than half of my time is spent on managing null pointer issue in my code, provided I have to keep track of current, previous and runners sometimes.

I need to know is there any way / model to deal with such issues?

Example:

public void deleteMid() {
    Node n = this;
    if (n.next == null) return;
    Node faster = this;
    Node prev = null;
    while (faster != null && faster.next != null) {
      prev = n;
      n = n.next;
      faster = faster.next.next;
    }
    prev.next = n.next;
  }

What are common pitfalls which should be avoided while mutating a list? are there any metal models which can help us to avoid those pitfalls?

closed as unclear what you're asking by gnat, Andres F., Kramii, Jörg W Mittag, dagnelies Oct 14 '16 at 19:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    It is not at all clear to me what you are trying to do in this routine. Perhaps you should consider adding explanatory comments, describing what the data structure is REALLY doing. It LOOKS like a singly-linked list, but you can't delete an element from a singly-linked list unless you have a pointer to the preceding element, and there is no such pointer available from the sublist "to the right" of the element to be deleted. So what's REALLY going on here? – John R. Strohm Oct 11 '16 at 19:59
  • 1
    @JohnR.Strohm The preceding element is prev. – coredump Oct 11 '16 at 22:17
  • @JohnR.Strohm I have three pointers to keep track of the current, previous and lookahead pointers. – CodeYogi Oct 12 '16 at 2:22
  • Is the list circular or not? – John R. Strohm Oct 12 '16 at 14:40
  • @JohnR.Strohm no its not circular. – CodeYogi Oct 13 '16 at 5:42
5

As I understand your post, there are two questions here. One is how to build a mental model of a linked list. The other is how to deal with all of the checks for null.

If you want a simple model to think about linked lists, it would have to be this:

train (locomotive and wagons)

You have an important node which is the head, and from there you start going from node to node until you reach the end. It's like being inside a train. You go from wagon to wagon until you reach the last one. Adding and deleting nodes is like adding and removing wagons from the train. You have to connect the end of one node (or wagon) to the next node (or wagon).

In the linked list you have nodes that keep a reference to the next node. That's how you move through the list. The last node has no more nodes after it and you have to mark that somehow. In the train, when you see no more wagons then you are in the last wagon. In the linked list when you see a null reference you know there are no more nodes.

So null is important because it marks the last node, the node which links to no other nodes. But null is also a bit dangerous. Your code is general. You go from one node to node.next. And if node.next points to nowhere, if you do node.next.next you get a NullPointerException which crashes your program.

There is not much you can do if you want your code to work but to check for null in various places. You could separate the null checking and extract it in some method and have something like if (hasNext(node)) { or if (node.hasNext()) {, etc and move the null verification there. This way your code is more explicit in saying what it's doing instead of knowing for what all those checks for null are. But like I said, there is not much you can do. That's the nature of the linked list.

1

In my experience, drawing diagrams is a big help. Also suitable names reduce the likelihood of errors... next and prev are understandable, but what does faster mean in your code?

  • One pointer iterates over nodes at position 0, 1, 2, ..., the faster one over nodes at 0, 2, 4, 6, ... When the faster one reaches the end of the linked list, the slower is in the middle of the list. – coredump Oct 11 '16 at 21:32
-3

You have every right to feel perplexed. The "null hack" obfuscates the core idea of many data structures. As you stated, the concept here is very simple: we can represent a linked list as a box-and-pointer diagram.

But how do we deal with all those pesky null pointers? If we accept the fact that a data structure is just another type, then we can take the "functional" view of a linked list:

type List a = Nil | Cons of a * List a

This definition is standard. A list is either the empty list, Nil, or the Cons (joining) of an element (of the correct type) with another list.

Note that there are no pointers in this definition. In particular, Nil is just a label: it is not the same as null, and it is most certainly not a pointer. Using null to represent an empty list is just a hack used by languages that lack sum types.

  • 3
    The answer is not helpful, you are arguing about treating empty lists as a "Nil" value instead of a "null" value, which does not help working with mutable nodes, in an imperative fashion. This is more a rant against null than anything else. – coredump Oct 11 '16 at 21:37
  • The OP says he is confused by null. I agree that null is confusing and offer an alternative that is (IMO) easier to think about. Considering the question is rather vague in what the OP specifically is looking for, I think this is quite helpful. – gardenhead Oct 11 '16 at 21:43
  • 1
    You could try re-writing this answer in a Java-like pseudocode. Someone confused by null is unlikely to understand your notation. – Andres F. Oct 12 '16 at 0:02
  • @Andres I could, but I don't see how that would help either. This isn't stack overflow, so just giving the OP the correct code is not really the point. ProgrammersSE, from what I understand, is related to software development practice in general. But to be honest I don't exactly know what the conceptual hurdle is that OP wants to overcome. I mean, I get it, writing a correct linked list implementation is surprisingly tricky. That's why every undergrad CS program has you doing it. But I don't know how to advice, so I just took a "shot in the dark" to provide an alternative. – gardenhead Oct 12 '16 at 0:21
  • 3
    @gardenhead Ok, ok, it was just an opinion. I wouldn't use ML/Haskell-like pseudocode which the OP is sure not to understand; as a general pedagogical rule, I'd approach any answer using the same kind of "language" (in the broadest sense of the word) that the person asking the question is using. But that's just me. – Andres F. Oct 12 '16 at 0:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.