Top List List

In which list last node is point to the first?

CS240 -- Lecture Notes: Doubly Linked Lists and Circularly Linked Lists

Doubly Linked List

Different from a singly linked list, a doubly linked list allows us to go in both directions -- forward and reverse. Such lists allow for a great variety of quick update operations, including insertion and removal at both ends, and in the middle. A node in a doubly linked list stores two references -- a next link, which points to the next node in the list, and a prev link, which points to the previous node in the list.

It is usually convenient to add special nodes at both ends of a doubly linked list, a header node just before the head of the list, and a trailer node just after the tail of the list. These dummy or sentinel nodes do not store any elements. The header has a valid next reference by a null prev reference, while the trailer has a valid prev reference by a null next reference. A linked list object would simply need to store references to these two sentinels and a size counter that keeps track of the number of elements [not counting sentinels] in the list.

Let's look at the Java class DNode representing a node of a doubly linked list that stores a character string.

/** Node of a doubly linked list of strings */
public class DNode {
protected String element; // String element stored by a node
protected DNode next, prev; // Pointers to next and previous nodes
/** Constructor that creates a node with given fields */
public DNode[String e, DNode p, DNode n] {
element = e;
prev = p;
next = n;
}
/** Returns the element of this node */
public String getElement[] { return element; }
/** Returns the previous node of this node */
public DNode getPrev[] { return prev; }
/** Returns the next node of this node */
public DNode getNext[] { return next; }
/** Sets the element of this node */
public void setElement[String newElem] { element = newElem; }
/** Sets the previous node of this node */
public void setPrev[DNode newPrev] { prev = newPrev; }
/** Sets the next node of this node */
public void setNext[DNode newNext] { next = newNext; }
}

Insertion/Deletion

Insertion or deletion at the first node or the last node would be relatively easy with the introduction of both the prev and next link. Look at the above figure, it demonstrates the process of adding/removing an element at either ends.

Algorithm addFirst[v]:
w = header.getNext[] // the current first node
v.setNext[w]
w.setPrev[v]
header.setNext[v]
v.setPrev[header]
size++

Algorithm removeLast[]:
v = trailer.getPrev[] // the current last node
if [v = = header] then
Indicate an error: the list is empty
prev = v.getPrev[]
prev.setNext[trailer]
trailer.setPrev[prev]
v.setPrev[null]
v.setNext[null]
size--

Will the above algorithms work for special cases such as empty lists? Write the algorithms for removing the first node and insertion at the last node.

Before, we have discussed insertion in the middle of a linked list, which might be difficult to implement on a singly linked list, but easy to implement on a doubly linked list. The two-way linking makes a doubly linked list convenient for maintaining a list of elements while allowing for insertion and removal in the middle of the list. Given a node v of a doubly linked list, we can easily insert a new node z immediately after v.

Algorithm addAfter[v, z]:
w = v.getNext[]
v.setNext[z]
z.setPrev[v]
z.setNext[w]
w.setPrev[z]
size++

What about inserting a new node z immediately before v?

The following code shows the the book implementation [reference book] of the doubly linked list.

/** Doubly linked list with nodes of type DNode storing strings. */
public class DList {
protected int size; // number of elements
protected DNode header, trailer; // sentinels
/** Constructor that creates an empty list */
public DList[] {
size = 0;
header = new DNode[null, null, null]; // create header
trailer = new DNode[null, header, null]; // create trailer
header.setNext[trailer]; // make header and trailer point to each other
}
/** Returns the number of elements in the list */
public int size[] { return size; }
/** Returns whether the list is empty */
public boolean isEmpty[] { return [size == 0]; }
/** Returns the first node of the list */
public DNode getFirst[] throws IllegalStateException {
if [isEmpty[]] throw new IllegalStateException["List is empty"];
return header.getNext[];
}
/** Returns the last node of the list */
public DNode getLast[] throws IllegalStateException {
if [isEmpty[]] throw new IllegalStateException["List is empty"];
return trailer.getPrev[];
}
/** Returns the node before the given node v. An error occurs if v
* is the header */
public DNode getPrev[DNode v] throws IllegalArgumentException {
if [v == header] throw new IllegalArgumentException
["Cannot move back past the header of the list"];
return v.getPrev[];
}
/** Returns the node after the given node v. An error occurs if v
* is the trailer */
public DNode getNext[DNode v] throws IllegalArgumentException {
if [v == trailer] throw new IllegalArgumentException
["Cannot move forward past the trailer of the list"];
return v.getNext[];
}
/** Inserts the given node z before the given node v. An error
* occurs if v is the header */
public void addBefore[DNode v, DNode z] throws IllegalArgumentException {
DNode u = getPrev[v]; // may throw an IllegalArgumentException
z.setPrev[u];
z.setNext[v];
v.setPrev[z];
u.setNext[z];
size++;
}
/** Inserts the given node z after the given node v. An error occurs
* if v is the trailer */
public void addAfter[DNode v, DNode z] {
DNode w = getNext[v]; // may throw an IllegalArgumentException
z.setPrev[v];
z.setNext[w];
w.setPrev[z];
v.setNext[z];
size++;
}
/** Inserts the given node at the head of the list */
public void addFirst[DNode v] {
addAfter[header, v];
}
/** Inserts the given node at the tail of the list */
public void addLast[DNode v] {
addBefore[trailer, v];
}
/** Removes the given node v from the list. An error occurs if v is
* the header or trailer */
public void remove[DNode v] {
DNode u = getPrev[v]; // may throw an IllegalArgumentException
DNode w = getNext[v]; // may throw an IllegalArgumentException
// unlink the node from the list
w.setPrev[u];
u.setNext[w];
v.setPrev[null];
v.setNext[null];
size--;
}
/** Returns whether a given node has a previous node */
public boolean hasPrev[DNode v] { return v != header; }
/** Returns whether a given node has a next node */
public boolean hasNext[DNode v] { return v != trailer; }
/** Returns a string representation of the list */
public String toString[] {
String s = "[";
DNode v = header.getNext[];
while [v != trailer] {
s += v.getElement[];
v = v.getNext[];
if [v != trailer]
s += ",";
}
s += "]";
return s;
}
}

Exercises

Traverse the doubly linked list in a reverse order
Print out the contents of the ith node
Delete a node with a specific data field in the doubly linked list
Delete all nodes with a specific data field in the doubly linked list
How to compare two lists to see if they are the same?

Circularly Linked List

A circularly linked list is a special linked list, which could be an extension of the singly or doubly linked lists we learned before. It also has many forms: with a dummy head node or non-dummy head node.

The circularly linked list in the reference book has the same kind of nodes as a singly linked list. Each node has a next pointer and a reference to an element. But there is no head or tail in a circularly linked list. Instead of having the last node's next pointer be null, it points back to the first node. Thus, there is no first or last node. We can traverse the list from any node. We use a cursor node to allow us to have a place to start from if we ever need to traverse a circularly linked list. There are three basic operations with the circularly linked list:

add[v]: Insert a new node v immediately after the cursor; if the list is empty, then v becomes the cursor and its next pointer points to itself.
remove[]: Remove and return the node v immediately after the cursor [not the cursor itself, unless it is the only node]; if the list becomes empty, the cursor is set to null.
advance[]: Advance the cursor to the next node in the list.

Note in some sense, cursor points to the current "last node", so cursor.next points to the first node. The first node is removed, a new node becomes the new first node.

/** Circulary linked list with nodes of type Node storing strings. */
public class CircleList {
protected Node cursor; // the current cursor
protected int size; // the number of nodes in the list
/** Constructor that creates and empty list */
public CircleList[] { cursor = null; size = 0; }
/** Returns the current size */
public int size[] { return size; }
/** Returns the cursor */
public Node getCursor[] { return cursor; }
/** Moves the cursor forward */
public void advance[] { cursor = cursor.getNext[]; }
/** Adds a node after the cursor */
public void add[Node newNode] {
if [cursor == null] { // list is empty
newNode.setNext[newNode];
cursor = newNode;
}
else {
newNode.setNext[cursor.getNext[]];
cursor.setNext[newNode];
}
size++;
}
/** Removes the node after the cursor */
public Node remove[] {
Node oldNode = cursor.getNext[]; // the node being removed
if [oldNode == cursor]
cursor = null; // list is becoming empty
else {
cursor.setNext[oldNode.getNext[]]; // link out the old node
oldNode.setNext[null];
}
size--;
return oldNode;
}
/** Returns a string representation of the list, starting from the cursor */
public String toString[] {
if [cursor == null] return "[]";
String s = "[..." + cursor.getElement[];
Node oldCursor = cursor;
for [advance[]; oldCursor != cursor; advance[]]
s += ", " + cursor.getElement[];
return s + "...]";
}
}

Is the above code robust? Why or why not?

Applications of Linked Lists

Game "Duck, Duck, Goose" is a children's game, where everyone but one child sits in a circle. That one child walks around the outside of the circle. He/She pats each child on the head, saying "Duck" each time, until reaching a child that he/she identifiers as "Goose". At this point there is a mad scramble, as the "Goose" and the child race around the circle. Whoever returns to the Goose's former place first gets to remain in the circle. The loser of this race is the walking child for the next round of play. Simulating this game is an ideal application of a circularly linked list. How?

The walking around child can be identified as the person sitting after the cursor
Advance the cursor with each "Duck" the walking child identifies
Once a "Goose" is identified, remove the node from the list
Make a random decision to simulate whether "Goose" or the walking child win the race
Insert the winner back into the list

/** Simulation of Duck, Duck, Goose with a circularly linked list. */
public static void main[String[] args] {
CircleList C = new CircleList[];
int N = 3; // number of iterations of the game
Node it; // the player who is "it"
Node goose; // the goose
Random rand = new Random[];
rand.setSeed[System.currentTimeMillis[]]; // use current time as seed
// The players...
String[] names = {"Bob","Jen","Pam","Tom","Ron","Vic","Sue","Joe"};
for [int i = 0; i< names.length; i++] {
C.add[new Node[names[i], null]];
C.advance[];
}
for [int i = 0; i < N; i++] { // play Duck, Duck, Goose N times
System.out.println["Playing Duck, Duck, Goose for " + C.toString[]];
it = C.remove[];
System.out.println[it.getElement[] + " is it."];
while [rand.nextBoolean[] || rand.nextBoolean[]] { // march around circle
C.advance[]; // advance with probability 3/4
System.out.println[C.getCursor[].getElement[] + " is a duck."];
}
goose = C.remove[];
System.out.println[goose.getElement[] + " is the goose!"];
if [rand.nextBoolean[]] {
System.out.println["The goose won!"];
C.add[goose]; // add the goose back in its old place
C.advance[]; // now the cursor is on the goose
C.add[it]; // The "it" person will be it again in next round
}
else {
System.out.println["The goose lost!"];
C.add[it]; // add who's "it" back at the goose's place
C.advance[]; // now the cursor is on the "it" person
C.add[goose]; // The goose will be "it" in the next round
}
}
System.out.println["Final circle is " + C.toString[]];
}

Sorting Linked List

Apply the insertion-sort algorithm on a doubly linked list.

/** Insertion-sort for a doubly linked list of class DList. */
public static void sort[DList L] {
if [L.size[] 0]
ins = ins.getPrev[]; // move left
L.addAfter[ins,pivot]; // add the pivot back, after insertion point
if [ins == end] // we just added pivot after end in this case
end = end.getNext[]; // so increment the end marker
}
}

Conclusion

Like arrays, linked lists are used as a building block for many other data structures, such as stacks, queues and their variations. A linked list data structure might work well in one case, but cause problems in another. There are some common tradeoffs involving linked list structures. In general, if you have a dynamic collection, where elements are frequently being added and deleted, and the location of new elements added to the list is significant, then benefits of a linked list increase.

Linked lists vs. arrays

Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented.
Array allows random access, while linked lists allow only sequential access to elements.
Extra storage is needed for linked lists for references, which often makes them impractical for lists of small data items such as characters or boolean values.

Doubly linked vs. singly linked

Doubly linked lists require more space per node, and their operations are more expensive; but they are easier to manipulate because they allow sequential access in both directions.
For example, insert or delete a node in constant number of operations given only that node's address.

Circularly linked vs. linearly linked

Circular linked lists are most useful for describing naturally circular structures, and have the advantage of a regular structure and being able to traverse the list starting at any point. They also allow quick access to the first and last records through a single pointer [the address of the last element]. Their main disadvantage is the complexity of iteration, which has subtle special cases.

Sentinel nodes

Sentinel nodes may simplify certain list operations, by ensuring that the next and/or previous nodes exist for every element. However sentinel nodes use up extra space [especially in applications that use many short lists], and they may complicate other operations. To avoid the extra space requirement the sentinel nodes can often be reused as references to the first and/or last node of the list.

Last updated: Jan. 2011

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề