Delete elements within a Linked List

Question

Looking for help again as my professor seems to do an awful job of explaining things (assumes that we know way too much about java programming, when in fact, it's the first java class most of us are taking).

Not looking for someone to write the code for me, but rather someone who can let me know if I'm on the right track and guide me in the right direction. I really want to learn this stuff, not be spoon-fed it, but the professor is making it very hard to do so, so I turn here for help.

The question is to take a LinkedList and create a function to delete the k-th element in that list. I have figured out how to remove the first item if k == 0, but I'm getting lost on how to access the proper element for the "k" within my loop. Here's what I have so far:

public class MyLinked {
  static class Node {
    public Node(double item, Node next) {
      this.item = item;
      this.next = next;
    }

    public double item;
    public Node next;
  }

  int N;
  Node first;
  // delete the kth element (where k is between 0 and N-1 inclusive)
  public void delete(int k) {
    if (k < 0 || k >= N) throw new IllegalArgumentException();
    {
      if (k == 0) {
        remove(first.item);
      } else if (k > 0) {
        kElem = LinkedList.get();
        remove(kElem);
      }
    }
  }
}

I'm trying to assign a variable to the .get function but I am definitely wrong there, but not quite sure how to go about this. I know I need to get the value of the k-th element and delete it, however.

I'm also aware that after this, I need to adjust the pointers within the LinkedList to fill the gap where the element I deleted would have been.

Thank you.

Answer 1

Your Link List looks like this:

On this image prev is the object in front of the object you want to delete. Cur is the object you want to delete.

You loop until the next-pointer targets the object you want to delete. After that you set the next pointer of prev to the the object, which follows cur (cur is the object you want to delete).

In pseudo-code it would look like this:

prev = head;
while(prev.next != cur) {
  prev = prev.next
}

After this step the prev is on the correct position.

You can see, that this algorithm works with every case except removing the head. You can make a check if you are removing the head and use a different algorithm or you use a dummy-node. Use the dummy-node as head and a dummy-node as tail (here not displayed, but used in double-linked-lists). This dummy-nodes are called sentinels. You won't ever remove this sentinel but your algorithm works without the additional-check because you will remove elements > 0.

Sources: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

In the comments I saw a discussion about clean-code. If you are learning clean-code you will see, that a lot of algorithms are easier to understand, if the variables express their purpose. For example N should be size. But in a different context it could be an upper-limit-of-elements for a cache. There is a good book on this topic: Clean Architecture: A Craftsman's Guide to Software Structure and Design (Robert C. Martin Series)

What do you think is easier to read:

int[][] a = new int[100][200];
for(int i = 0; i < a.length) {
  for(int j = 0; j < a[i].length) {
    a[i][j] = i*j;
  }
 }

or this:

 int[][] productOfRowColumns = new int[100][200];
 for(int row = 0; i < productOfRowColumns.length) {
  for(int column = 0; j < productOfRowColumns[row].length) {
    productOfRowColumns[row][column] = row*column;
  }
 }

Answer 2

First go to the k-1 element. Set element.next=element.next.next. Thats how you skip the element, which should be deleted.

Exception: When k=0 (the head element), just set head=head.next.

Optionally you can set next = null for the deleted element (when you went for k-1 elements, deleted=element.next before setting element.next=element.next.next. then say deleted.next=null to clear its next-pointer.

---

There is also a second common way where you go to the kth element, but you always save the previous (k-1) element in a variable. Performance wise it is worse, because you update 2 variables in each step. It could be more intuitive. Check that video: https://www.youtube.com/watch?v=2RwWsHePdr8 (I hope yt-links are allowed on SO)

---

By the way, your

  static class Node {
    public Node(double item, Node next) {
      this.item = item;
      this.next = next;
    }

    public double item;
    public Node next;
  }

  int N;
  Node first;

is your implementation of the list. LinkedList is the implementation provided by java. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html. You can not mix them.

---

Hints:

• Don't forget to decrease the size of the list (N--;)
• You can "go" to the n-th element with "Node current=head; for(int i = 0; i < n; i++) current=current.next;"
• What I mean with "head" is your "first". It is the first element of the list.

Answer 3

The "get" method does not do what you want. You will need to write the code to iterate to position k-1 and switch the pointer, as you said:-

eg. list 1->2->3->4, k=2

iterate using next pointer upto 2, switch the next pointer to point to 4. You don't need to do anything else(remove etc)