5 Replies - 3919 Views - Last Post: 06 September 2012 - 02:14 PM Rate Topic: -----

#1 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

(Circular) Linked Lists

Posted 05 September 2012 - 05:35 PM

I want to start using different data structures. I am trying to start using linked lists more and circular linked lists. However I am not sure if my logic is correct.(This is not a homework assignment)

Linked Lists...
I know that to create a linked list you need a node class, a head and a tail.

Circular LinkedLists...
They are similar to linked lists, the tail is just the same as the head right?

So if I wanted to create a circular linked list within a class and add to it, is this logic correct?


import java.util.*;

public class learning

{
LinkedList<Integer> books = new LinkedList<>();
Node head;
Node tail;
public learning()
{
head =null;
tail =null;

head =tail;
}

//this is where I begin to get a little confused. Let's say I want to add books to my learning library:

  public void addBooks ( int n)//the number of books I want to add to the library
     

        for (int i=0; i<n-1;i++) 
        {
            list.add(i);
        }
        for (int i=0; i<n-1;i++)//this loop sets the new nodes next node to the old node
        {
            list.get(i);
      
        }
}
}




The program always seems to compile, but when I try my add method, nothing seems to be added. I even tried making a test class and nothing still showed up.

Thanks for any advice

Is This A Good Question/Topic? 0
  • +

Replies To: (Circular) Linked Lists

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: (Circular) Linked Lists

Posted 05 September 2012 - 05:43 PM

View PostJavaLilly, on 05 September 2012 - 08:35 PM, said:

Linked Lists...
I know that to create a linked list you need a node class, a head and a tail.

Circular LinkedLists...
They are similar to linked lists, the tail is just the same as the head right?

A LinkedList does not have a tail
it just have a head with a pointer to the next node, which has a pointer to the next node, which has ... until that pointer becomes null

A circular LinkList has a head and a tail. A next node pointer and a previous node pointer. The tail next node pointer is the head.
The head previous node pointer is the head.
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: (Circular) Linked Lists

Posted 06 September 2012 - 05:12 AM

View PostJavaLilly, on 06 September 2012 - 02:35 AM, said:

I know that to create a linked list you need a node class, a head and a tail.


Right.

Quote

Circular LinkedLists...
They are similar to linked lists, the tail is just the same as the head right?


No. First let's clarify what you're talking about when you say "tail":

Sometimes the word tail is used to refer to the last node in a list. In a circular linked list, the first node of the list is most certainly not the same as the last. The only connection between the last node of a list and circular lists is that when you have a circular doubly linked list, you won't need to keep track of the last node because the last node will be the predecessor of the first node.

Other times the word tail is used to refer to the rest of the list, i.e. a Node might have a member called "head" that contains its value and a member called "tail" that points to the next node in the list. Using this nomenclature, obviously the "tail" of a node can't be the same as its head because they have different types. You could make the tail point to the node itself, but that'd just give you one single circular node.

What makes a circular linked list different from a regular linked list is that the successor (or "tail") of the last node in the list will be the first node in the list. And in case of a doubly linked list the predecessor of the first node in the list will also be the last node in the list.

Quote

So if I wanted to create a circular linked list within a class and add to it, is this logic correct?


import java.util.*;

public class learning

{
LinkedList<Integer> books = new LinkedList<>();
Node head;
Node tail;
public learning()
{
head =null;
tail =null;

head =tail;
}



No. You can't turn java.util.LinkedList into a circular list by wrapping it in a class with a head and tail variable. That makes no sense. You also can't mess with the nodes of a java.util.LinkedList to make it circular because those are private and not accessible to you. So the only way to make a circular linked list is to implement one yourself or use a third party implementation.

View Postpbl, on 06 September 2012 - 02:43 AM, said:

A LinkedList does not have a tail


Sure, it does. If we take "tail" to mean "a reference to the last node in the list", then most implementations of linked lists (both doubly and singly linked lists) have one - without it inserting at the end of a list would be O(n).

Quote

A circular LinkList has a head and a tail. A next node pointer and a previous node pointer. The tail next node pointer is the head.
The head previous node pointer is the head.


I think you're mixing up the differences between doubly linked vs. singly linked and circular vs. non-circular here.

Every (sane implementation of a mutable) linked list has a reference to the tail of the list. It doesn't matter whether it's singly linked or doubly linked, circular or not circular.

Every doubly linked list has "A next node pointer and a previous node pointer". Whether it's circular or not.

Only the "The tail next node pointer is the head. The head previous node pointer is the head" part is specific to circular doubly linked lists.

Note that there are also circular singly linked lists. For those the next pointer of the tail will be the head and previous pointers don't exist.

This post has been edited by sepp2k: 06 September 2012 - 08:24 AM

Was This Post Helpful? 2
  • +
  • -

#4 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

Re: (Circular) Linked Lists

Posted 06 September 2012 - 05:49 AM

Alright, first off, when I say tail, I talking about the last node in a linked list with a null value. I was pretty sure you had to have one of those or else the linked list wouldn't have an official end.

Second- so, what you are saying is this:

A linked list is a data structure with a head and a tail(in the sense of the last node).
A circular linked list still has both a head and a tail node(which are separate) its just that the pointer from the tail points to the head.

Then, there is the doubly linked list which sounds similar to the circular linked list.

Lastly, what do you mean "the previous pointers don't exist"?



[quote name='sepp2k' date='06 September 2012 - 05:12 AM' timestamp='1346933567' post='1697325']

View PostJavaLilly, on 06 September 2012 - 02:35 AM, said:

I know that to create a linked list you need a node class, a head and a tail.


Right.

This post has been edited by macosxnerd101: 06 September 2012 - 07:27 AM
Reason for edit:: Removed long quote

Was This Post Helpful? 0
  • +
  • -

#5 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: (Circular) Linked Lists

Posted 06 September 2012 - 05:55 AM

View PostJavaLilly, on 06 September 2012 - 02:49 PM, said:

Alright, first off, when I say tail, I talking about the last node in a linked list with a null value. I was pretty sure you had to have one of those or else the linked list wouldn't have an official end.


A circular list doesn't have an end. That's what "circular" means. It goes round and round in circles.

Quote

A linked list is a data structure with a head and a tail(in the sense of the last node).
A circular linked list still has both a head and a tail node(which are separate) its just that the pointer from the tail points to the head.


Right.

Quote

Then, there is the doubly linked list which sounds similar to the circular linked list.


It's not.

Quote

Lastly, what do you mean "the previous pointers don't exist"?


I mean a doubly linked list has a "next" pointer that points to the next node and a "previous" pointer that points to the previous node. A singly linked list only has a "next" pointer - no "previous" pointer.
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: (Circular) Linked Lists

Posted 06 September 2012 - 02:14 PM

View PostJavaLilly, on 06 September 2012 - 08:49 AM, said:

Alright, first off, when I say tail, I talking about the last node in a linked list with a null value.

Usually the last (tail) node as a null value for its forward pointer but not a null value.
You can imagine a List with multiple node having a null value. That would be perfectly legitimate.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1