Programming Forums > Application Development > Java

elford · Jan 6th, 2006, 4:30 PM

This is so simple, yet I can't understand why it won't work.

I'm trying to implement a linked list where insertions occur at the tail.

I have the constructors

(Toggle Plain Text)

	public SInfo() {
		head = null;
		tail = null;
	}

	public SInfo(SInfoNode m) {
		head = m;
		m.next = tail;
	}

Here is my insert method:

(Toggle Plain Text)

	public void insert(SInfoNode nodeToInsert) {
		if (head == null) {
			head = nodeToInsert;
			nodeToInsert.next = tail;
		} else {
			tail = nodeToInsert;
			nodeToInsert.next = tail;
		}
	}

This code worked fine with insertion at the head (with a different insert method of course). I've tried a lot of different things for insertion at the tail, but when I run the program, it runs without ceasing. What am I missing?

para · Jan 6th, 2006, 4:53 PM

You forget to set the current tail->next to be the new node.

If you want to add at the end, try something like this:
tail->next = nodeToInsert;
tail = nodeToInsert;

Ooble · Jan 6th, 2006, 8:50 PM

I'm confused... why do you need a tail pointer in the first place?

(Toggle Plain Text)

	public SInfo() {
		head = null;
	}
	
	public SInfo(SInfoNode m) {
		head = m;
		m.next = null;
	}
	
	public void insert(SInfoNode nodeToInsert) {
		while (head != null) {
			head = head.next;
		}
		head = nodeToInsert;
		head.next = null;
	}

para · Jan 6th, 2006, 9:12 PM

Quote:

Originally Posted by Ooble

I'm confused... why do you need a tail pointer in the first place?

Faster to add to the end, you don't have to go through the whole list to find the last node.

elford · Jan 6th, 2006, 11:09 PM

Quote:

Originally Posted by para

Faster to add to the end, you don't have to go through the whole list to find the last node.

Exactly it. In lists where order of the nodes matters, such as a queue, it allows you to insert in constant time, as opposed to looping through the list every time when you need to add at the end, which takes n^2 time.

I'll spare you the detailed algorithmic analysis.

Ooble · Jan 6th, 2006, 9:23 PM

Makes sense, I guess.

elford · Jan 6th, 2006, 11:13 PM

The solution proposed by para does work. One small modification tho, my constructors had an error too

(Toggle Plain Text)

public SwipeInfo() {
		head = null;
		tail = null;
	}
public SwipeInfo(SwipeInfoNode m) {
		head = m;
		tail = m;
	}

groovicus · Jan 6th, 2006, 11:30 PM

Quote:

as opposed to looping through the list every time when you need to add at the end, which takes n^2 time.

I must have missed something. How do you figure going through a list once is order n^2? There are only n elements, and you only need to iterate through them once.

elford · Jan 7th, 2006, 12:50 AM

Quote:

Originally Posted by groovicus

I must have missed something. How do you figure going through a list once is order n^2? There are only n elements, and you only need to iterate through them once.

I wasn't clear, and I made a mistake. It takes n time when doing insertions, not n^2. Figure that you start with a list of 5 nodes, and then you insert another node at the end (w/o the tail pointer). The loop must excute 5 times to insert. Then you insert a second element. The loop must execute 6 times. Then 7 time...etc.

When you add a series of numbers together like 5 + 6 + 7 + (n - 1) + n, where n is the highest number you will reach, the sum of all those numbers turns into the arithmetic series. That simplifies to order n. Thus, it take linear time to do the insertions, i.e. the time it takes to do the insertion is directly proportional to the size of the list...the list doubles in size, so does the time.

Why do something in linear time when you can do much better in constant time with an extra tail pointer? :p

groovicus · Jan 7th, 2006, 10:04 AM

Quote:

I wasn't clear, and I made a mistake.

I already knew that. We know how to do asymptotic analysis too

Jan 6th, 2006, 4:30 PM	#1
elford Programmer Join Date: Nov 2005 Posts: 35 Rep Power: 0	Linked list insertion at the tail This is so simple, yet I can't understand why it won't work. I'm trying to implement a linked list where insertions occur at the tail. I have the constructors (Toggle Plain Text) public SInfo() { head = null; tail = null; } public SInfo(SInfoNode m) { head = m; m.next = tail; } public SInfo() { head = null; tail = null; } public SInfo(SInfoNode m) { head = m; m.next = tail; } Here is my insert method: (Toggle Plain Text) public void insert(SInfoNode nodeToInsert) { if (head == null) { head = nodeToInsert; nodeToInsert.next = tail; } else { tail = nodeToInsert; nodeToInsert.next = tail; } } public void insert(SInfoNode nodeToInsert) { if (head == null) { head = nodeToInsert; nodeToInsert.next = tail; } else { tail = nodeToInsert; nodeToInsert.next = tail; } } This code worked fine with insertion at the head (with a different insert method of course). I've tried a lot of different things for insertion at the tail, but when I run the program, it runs without ceasing. What am I missing?

Jan 6th, 2006, 8:50 PM	#3
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	I'm confused... why do you need a tail pointer in the first place? (Toggle Plain Text) public SInfo() { head = null; } public SInfo(SInfoNode m) { head = m; m.next = null; } public void insert(SInfoNode nodeToInsert) { while (head != null) { head = head.next; } head = nodeToInsert; head.next = null; } public SInfo() { head = null; } public SInfo(SInfoNode m) { head = m; m.next = null; } public void insert(SInfoNode nodeToInsert) { while (head != null) { head = head.next; } head = nodeToInsert; head.next = null; } __________________ Me :: You :: Them

Jan 6th, 2006, 9:23 PM	#6
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Makes sense, I guess. __________________ Me :: You :: Them

Jan 6th, 2006, 11:13 PM	#7
elford Programmer Join Date: Nov 2005 Posts: 35 Rep Power: 0	The solution proposed by para does work. One small modification tho, my constructors had an error too (Toggle Plain Text) public SwipeInfo() { head = null; tail = null; } public SwipeInfo(SwipeInfoNode m) { head = m; tail = m; } public SwipeInfo() { head = null; tail = null; } public SwipeInfo(SwipeInfoNode m) { head = m; tail = m; }

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode

Jan 6th, 2006, 4:53 PM	#2
para Programmer Join Date: Dec 2005 Posts: 65 Rep Power: 3	You forget to set the current tail->next to be the new node. If you want to add at the end, try something like this: tail->next = nodeToInsert; tail = nodeToInsert;

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Linked list insertion at the tail