How to update rear in a circular linked list?

I need help updating the rear of a circular linked list if I move a set of nodes after the initial rear.

Lets assume rear is the rear node and rear.next circulates back to [1].

[1][2][3][4][5]  
<-------------/

If I move [1][2][3] after node [5] giving me

[4][5][1][2][3], which breaks the circular linked lis开发者_JS百科t,

How can I approach updating [3] as rear and rear.next to point to [1]?

Because the nature of the set of links is a circle, you have to break the links and reestablish them after moving. The important links here are the ones that are going to be 'broken', which is (if it is a singly linked list, as I am assuming), the link from [3] -> [4] and the link from [5] -> [1].

You have two sections in your list here, [1][2][3], which we can call A, and [4][5], which we can call B. The --> link shown below is the pointer to the first element in the list.

--> A -> B -+ 
    ^       |
    |       | 
    +-------+

What you want to do is reset the link so that the last element in A points to the first element in B, and the last element in B points to the first element in A. In addition, the beginning of the list is now the first element in B.

--> B -> A -+
    ^       |
    |       | 
    +-------+

So now we just break and reset the links where they are needed.

--> [1][2][3] -> [4][5] -+         --> [4][5] -> [1][2][3] -+
     ^                   |    =>        ^                   |
     +-------------------+              +-------------------+

• Set the beginning of the list to be the first element of B, which is [4]
• Set the last element in B, which is [5], to point to the first element in A, which is [1]. This happens to already be set that way, but don't count on that. :)
• Set the last element in A, which is [3], to point to the first element in B, which is [4].

As you can see, the only nodes we really care about are the first and last elements of each part of the list, i.e., the beginning and ending element of A and B. In this case, one of those sections also containd the first element, so we had to move the notion of which element was the 'first' element. Hope this helps.

Is this homework?

How are you doing the "move"?

I would make it a function, something like list.move(first, last, after), which in this case would be list.move(1, 3, 5).

And you'd have variables tracking the front/head and the rear/tail of the list. I'll assume they're called list.front and list.rear.

So in every case, you want to do:

list[after].next = list[first]

and then there's two special cases I can see:

• inserting after the rear
  (list[after] == list.rear)
• moving the head
  (list[start] == list.front)

So you can handle those using if statements.

I think this answers it(provided i understand this correctly)

Node insertAtRear(Node rear, T value) {
  Node tmp = new Node(value);
  if(rear!=null) {
    tmp.next = rear.next;
    rear.next = tmp
    rear = tmp
  } else {
    // this is probably the first element to be inserted
    rear = tmp;
    rear.next = rear;
  }
}

Working on the basis that you start with [1][2][3][4][5] and you want to end up with [4][5][1][2][3] you can do this using pointers and not change the data structure.

As you have indicated we have a circular list where the pointer "rear.next" points to the first bucket and each subsequent bucket has a .next pointer linking it to its right most neighbour until we get back to the rear bucket again. Basically a bunch of buckets linked to one another.

If we create a "tail" node and a "header" node we can use these to order the list. These are markers and not part of the circle they just point to a start or end point.

So to get [1][2][3][4][5] we can set the tail node to point to [5] then follow [5]s next pointer which leads us to [1] which we set our header to point to. So header=[1];tail=[5]

Starting at the header and working through the list following the next pointers each time we can access our items in this order [1][2][3][4][5]. No surprise there!

Lets change that though as we want [3] to be the rear. So lets set our tail node to point to [3]. Then follow [3]s next pointer we arrive at [4]. To this we assign the header.So header=[4];tail=[3]

Now working through our list starting with whatever our header points to we have [4][5][1][2][3].

It appears we have performed a move operation but we have not tampered with our data structure or its links - just the way we work with it. All we have altered is our header and tail. (Our pointers). Thats the beauty of the circular list.