CS: linked list confusion (Java)

In summary, the previous tail node (pointed to by tail) is set to point to the new node, which then becomes the new tail.
  • #1
n00neimp0rtnt
15
0
I just took my final for Data Structures and there was a question on it dealing with linked lists. A part of the question really threw me off. It looked something like this:

Code:
public class Node
{
     int contents;
     Node next;
}

public class LinkedList
{
     Node head, tail;
}

public void bar(int c)
{
     newNode = new Node();
     newNode.contents = c;
     [B]tail.next = newNode;
     tail = newNode;
     newNode.next = null;[/B]
}

The part of concern is in bold. When I read this, it looks like in the first line, tail.next is getting set to the Node that the reference "newNode" is pointing to. In the SECOND line, however, tail is getting set to the Node that "newNode" points to. If I'm not mistaken, doesn't that just nullify the first statement as if it was never executed? What happens to tail.next? After the second statement, isn't tail.next pointing to the same Node that newNode.next points to? I thought it was a typo so I asked my professor and he simply said that "tail.next is not 'inside' tail; they are two separate things," which didn't really help much.
 
Physics news on Phys.org
  • #2
If the precondition for the method is that tail points to the last Node on the list, then this method appends a new node to the end of a single-linked list without iterating through the whole list. Regarding your 3 highlighted lines:

Line 1: The previous tail node (pointed to by tail) is set to point to the new node, that is, the new node will now come after the previous tail node.
Line 2: The new node is then set as the new tail.
Line 3: The next node for the new node is set to null since this it is currently the tail (with the given code this line is for better readability rather than for necessity; the next field already has the value null).
 
  • #3
Hmm...so line 2 kinda "pushes back" the old tail and sets newNode as the NEW tail?
 
  • #4
Thats one way of putting it. If you have trouble visualize it then make (or search for) a diagram that show what is pointing to what before and after the two lines.
 
  • #5
Ok, I think I get it now. I'm pretty sure I got the questions relating to it right because I had a hunch what the methods were supposed to do, it just bothered me that I didn't know how it worked.
 

1. What is a linked list in Java?

A linked list in Java is a data structure that consists of a sequence of nodes, where each node contains a value and a pointer to the next node in the list. It is a linear data structure where elements are not stored in contiguous memory locations, but are linked using pointers.

2. How do you create a linked list in Java?

To create a linked list in Java, you can use the LinkedList class provided by the Java Collections Framework. You can also create your own custom implementation by creating a Node class with a value and a pointer to the next node, and then creating methods to add, remove, and access nodes in the list.

3. How is a linked list different from an array in Java?

A linked list is different from an array in Java in terms of how elements are stored and accessed. In an array, elements are stored in contiguous memory locations and can be accessed directly using an index. In a linked list, elements are not stored in contiguous memory locations and can only be accessed sequentially by following the pointers from one node to the next.

4. What are the advantages of using a linked list in Java?

One advantage of using a linked list in Java is that it allows for efficient insertion and deletion of elements, as it does not require shifting of elements like an array does. It also allows for dynamic resizing, meaning elements can be added or removed without worrying about the size of the list. Additionally, linked lists can be used to implement other data structures such as stacks and queues.

5. What are some common operations performed on a linked list in Java?

Some common operations performed on a linked list in Java include adding or removing elements at the beginning or end of the list, inserting or deleting elements at a specific position, and searching for a specific element in the list. Other operations may also include traversing the list to perform a specific action on each element, such as printing or sorting.

Similar threads

  • Programming and Computer Science
Replies
9
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
6K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
11K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
Back
Top