If your first name starts with a letter from A-J inclusively:
Add a method swapTwoNodes to SinglyLinkedList class from week 2 lecture examples. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapTwoNodes method. Hint: You may need to traverse the list.
If your first name starts with a letter from K-Z inclusively:
Add a method swapTwoNodes to DoublyLinkedList class from week 2 lecture examples. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapTwoNodes method. Hint: You may need to traverse the list.
(4 marks)
If your first name starts with a letter from A-J inclusively:
Use the SinglyLinkedList implementation of the textbook (week 2 lecture examples. Write a method for concatenating two singly linked lists L1 and L2, into a single list L that contains all the nodes of L1 followed by all the nodes of L2. Write a main method to test the new method. Hint: Connect the end of L1 into the beginning of L2.
If your first name starts with a letter from K-Z inclusively:
Use the DoublyLinkedList implementation of the textbook (week 2 lecture examples. Write a method for concatenating two doubly linked lists L1 and L2, into a single list L that contains all the nodes of L1 followed by all the nodes of L2. Write a main method to test the new method. Hint: Connect the end of L1 into the beginning of L2.
(3 marks)
If your first name starts with a letter from A-J inclusively:
Implement the clone() method for the CircularlyLinkedList class. Make sure to properly link the new chain of nodes.
If your first name starts with a letter from K-Z inclusively:
Let L1 and L2 be two circularly linked lists created as objects of CircularlyLinkedList class from Lesson. Write a method that returns true if L1 and L2 store the same sequence of elements (but perhaps with different starting points). Write the main method to test the new method. Hint: Try to find a matching alignment for the first node of one list.
(3 marks)
/*
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
* Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package linkedlists;
/**
* A basic singly linked list implementation.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public class SinglyLinkedList<E> implements Cloneable {
//---------------- nested Node class ----------------
/**
* Node of a singly linked list, which stores a reference to its
* element and to the subsequent node in the list (or null if this
* is the last node).
*/
private static class Node<E> {
/** The element stored at this node */
private E element; // reference to the element stored at this node
/** A reference to the subsequent node in the list */
private Node<E> next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param n reference to a node that should follow the new node
*/
public Node(E e, Node<E> n) {
element = e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public E getElement() { return element; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node<E> getNext() { return next; }
// Modifier methods
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node<E> n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node<E> head = null; // head node of the list (or null if empty)
/** The last node of the list */
private Node<E> tail = null; // last node of the list (or null if empty)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the list
/** Constructs an initially empty list. */
public SinglyLinkedList() { } // constructs an initially empty list
// access methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of the list
* @return element at the front of the list (or null if empty)
*/
public E first() { // returns (but does not remove) the first element
if (isEmpty()) return null;
return head.getElement();
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() { // returns (but does not remove) the last element
if (isEmpty()) return null;
return tail.getElement();
}
// update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) { // adds element e to the front of the list
head = new Node<>(e, head); // create and link a new node
if (size == 0)
tail = head; // special case: new node becomes tail also
size++;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) { // adds element e to the end of the list
Node<E> newest = new Node<>(e, null); // node will eventually be the tail
if (isEmpty())
head = newest; // special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes the tail
size++;
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() { // removes and returns the first element
if (isEmpty()) return null; // nothing to remove
E answer = head.getElement();
head = head.getNext(); // will become null if list had only one node
size--;
if (size == 0)
tail = null; // special case as list is now empty
return answer;
}
@SuppressWarnings({"unchecked"})
public boolean equals(Object o) {
if (o == null) return false;
if (getClass() != o.getClass()) return false;
SinglyLinkedList other = (SinglyLinkedList) o; // use nonparameterized type
if (size != other.size) return false;
Node walkA = head; // traverse the primary list
Node walkB = other.head; // traverse the secondary list
while (walkA != null) {
if (!walkA.getElement().equals(walkB.getElement())) return false; //mismatch
walkA = walkA.getNext();
walkB = walkB.getNext();
}
return true; // if we reach this, everything matched successfully
}
@SuppressWarnings({"unchecked"})
public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
// always use inherited Object.clone() to create the initial copy
SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone(); // safe cast
if (size > 0) { // we need independent chain of nodes
other.head = new Node<>(head.getElement(), null);
Node<E> walk = head.getNext(); // walk through remainder of original list
Node<E> otherTail = other.head; // remember most recently created node
while (walk != null) { // make a new node storing same element
Node<E> newest = new Node<>(walk.getElement(), null);
otherTail.setNext(newest); // link previous node to this one
otherTail = newest;
walk = walk.getNext();
}
}
return other;
}
public int hashCode() {
int h = 0;
for (Node walk=head; walk != null; walk = walk.getNext()) {
h ^= walk.getElement().hashCode(); // bitwise exclusive-or with element's code
h = (h << 5) | (h >>> 27); // 5-bit cyclic shift of composite code
}
return h;
}
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node<E> walk = head;
while (walk != null) {
sb.append(walk.getElement());
if (walk != tail)
sb.append(", ");
walk = walk.getNext();
}
sb.append(")");
return sb.toString();
}
//main method
public static void main(String[] args)
{
SinglyLinkedList<String> list = new SinglyLinkedList<String>();
list.addFirst("MSP");
list.addLast("ATL");
list.addLast("BOS");
//
list.addFirst("LAX");
System.out.println(list);
//
}
}/*
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
* Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package linkedlists;
/**
* A basic doubly linked list implementation.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public class DoublyLinkedList<E> {
//---------------- nested Node class ----------------
/**
* Node of a doubly linked list, which stores a reference to its
* element and to both the previous and next node in the list.
*/
private static class Node<E> {
/** The element stored at this node */
private E element; // reference to the element stored at this node
/** A reference to the preceding node in the list */
private Node<E> prev; // reference to the previous node in the list
/** A reference to the subsequent node in the list */
private Node<E> next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param p reference to a node that should precede the new node
* @param n reference to a node that should follow the new node
*/
public Node(E e, Node<E> p, Node<E> n) {
element = e;
prev = p;
next = n;
}
// public accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public E getElement() { return element; }
/**
* Returns the node that precedes this one (or null if no such node).
* @return the preceding node
*/
public Node<E> getPrev() { return prev; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node<E> getNext() { return next; }
// Update methods
/**
* Sets the node's previous reference to point to Node n.
* @param p the node that should precede this one
*/
public void setPrev(Node<E> p) { prev = p; }
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node<E> n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the DoublyLinkedList
/** Sentinel node at the beginning of the list */
private Node<E> header; // header sentinel
/** Sentinel node at the end of the list */
private Node<E> trailer; // trailer sentinel
/** Number of elements in the list (not including sentinels) */
private int size = 0; // number of elements in the list
/** Constructs a new empty list. */
public DoublyLinkedList() {
header = new Node<>(null, null, null); // create header
trailer = new Node<>(null, header, null); // trailer is preceded by header
header.setNext(trailer); // header is followed by trailer
}
// public accessor methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of the list.
* @return element at the front of the list (or null if empty)
*/
public E first() {
if (isEmpty()) return null;
return header.getNext().getElement(); // first element is beyond header
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() {
if (isEmpty()) return null;
return trailer.getPrev().getElement(); // last element is before trailer
}
// public update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) {
addBetween(e, header, header.getNext()); // place just after the header
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) {
addBetween(e, trailer.getPrev(), trailer); // place just before the trailer
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() {
if (isEmpty()) return null; // nothing to remove
return remove(header.getNext()); // first element is beyond header
}
/**
* Removes and returns the last element of the list.
* @return the removed element (or null if empty)
*/
public E removeLast() {
if (isEmpty()) return null; // nothing to remove
return remove(trailer.getPrev()); // last element is before trailer
}
// private update methods
/**
* Adds an element to the linked list in between the given nodes.
* The given predecessor and successor should be neighboring each
* other prior to the call.
*
* @param predecessor node just before the location where the new element is inserted
* @param successor node just after the location where the new element is inserted
*/
private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
// create and link a new node
Node<E> newest = new Node<>(e, predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
/**
* Removes the given node from the list and returns its element.
* @param node the node to be removed (must not be a sentinel)
*/
private E remove(Node<E> node) {
Node<E> predecessor = node.getPrev();
Node<E> successor = node.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return node.getElement();
}
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node<E> walk = header.getNext();
while (walk != trailer) {
sb.append(walk.getElement());
walk = walk.getNext();
if (walk != trailer)
sb.append(", ");
}
sb.append(")");
return sb.toString();
}
//main method
public static void main(String[] args)
{
//create and populate a doubly linked list
DoublyLinkedList<String> list = new DoublyLinkedList<String>();
list.addFirst("MSP");
list.addLast("ATL");
list.addLast("BOS");
//
list.addFirst("LAX");
System.out.println(list);
System.out.println(list.first());
//
}
} //----------- end of DoublyLinkedList class -----------/*
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
* Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package linkedlists;
/**
* An implementation of a circularly linked list.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public class CircularlyLinkedList<E> {
//---------------- nested Node class ----------------
/**
* Singly linked node, which stores a reference to its element and
* to the subsequent node in the list.
*/
private static class Node<E> {
/** The element stored at this node */
private E element; // an element stored at this node
/** A reference to the subsequent node in the list */
private Node<E> next; // a reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param n reference to a node that should follow the new node
*/
public Node(E e, Node<E> n) {
element = e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public E getElement() { return element; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node<E> getNext() { return next; }
// Modifier methods
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node<E> n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the CircularlyLinkedList
/** The designated cursor of the list */
private Node<E> tail = null; // we store tail (but not head)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the list
/** Constructs an initially empty list. */
public CircularlyLinkedList() { } // constructs an initially empty list
// access methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of the list
* @return element at the front of the list (or null if empty)
*/
public E first() { // returns (but does not remove) the first element
if (isEmpty()) return null;
return tail.getNext().getElement(); // the head is *after* the tail
}
/**
* Returns (but does not remove) the last element of the list
* @return element at the back of the list (or null if empty)
*/
public E last() { // returns (but does not remove) the last element
if (isEmpty()) return null;
return tail.getElement();
}
// update methods
/**
* Rotate the first element to the back of the list.
*/
public void rotate() { // rotate the first element to the back of the list
if (tail != null) // if empty, do nothing
tail = tail.getNext(); // the old head becomes the new tail
}
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) { // adds element e to the front of the list
if (size == 0) {
tail = new Node<>(e, null);
tail.setNext(tail); // link to itself circularly
} else {
Node<E> newest = new Node<>(e, tail.getNext());
tail.setNext(newest);
}
size++;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) { // adds element e to the end of the list
addFirst(e); // insert new element at front of list
tail = tail.getNext(); // now new element becomes the tail
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() { // removes and returns the first element
if (isEmpty()) return null; // nothing to remove
Node<E> head = tail.getNext();
if (head == tail) tail = null; // must be the only node left
else tail.setNext(head.getNext()); // removes "head" from the list
size--;
return head.getElement();
}
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
if (tail == null) return "()";
StringBuilder sb = new StringBuilder("(");
Node<E> walk = tail;
do {
walk = walk.getNext();
sb.append(walk.getElement());
if (walk != tail)
sb.append(", ");
} while (walk != tail);
sb.append(")");
return sb.toString();
}
//main method
public static void main(String[] args)
{
//(LAX, MSP, ATL, BOS)
CircularlyLinkedList<String> circularList = new CircularlyLinkedList<String>();
circularList.addFirst("LAX");
circularList.addLast("MSP");
circularList.addLast("ATL");
circularList.addLast("BOS");
//
System.out.println(circularList);
circularList.removeFirst();
System.out.println(circularList);
circularList.rotate();
System.out.println(circularList);
//
}
}# -*- coding: utf-8 -*-
class Node:
def __init__(self, element, next_node=None):
self.element = element
self.next_node = next_node
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def __len__(self):
return self.size
def is_empty(self):
return self.size == 0
def first(self):
if self.is_empty():
return None
return self.head.element
def last(self):
if self.is_empty():
return None
return self.tail.element
def add_first(self, e):
newest = Node(e, next_node=self.head)
self.head = newest
if self.is_empty():
self.tail = self.head
self.size += 1
def add_last(self, e):
newest = Node(e)
if self.is_empty():
self.head = newest
else:
self.tail.next_node = newest
self.tail = newest
self.size += 1
def remove_first(self):
if self.is_empty():
return None
answer = self.head.element
self.head = self.head.next_node
self.size -= 1
if self.is_empty():
self.tail = None
return answer
def __eq__(self, other):
if not isinstance(other, SinglyLinkedList) or self.size != len(other):
return False
node1, node2 = self.head, other.head
while node1 is not None:
if node1.element != node2.element:
return False
node1, node2 = node1.next_node, node2.next_node
return True
def __str__(self):
result = []
node = self.head
while node is not None:
result.append(str(node.element))
node = node.next_node
return "(" + ", ".join(result) + ")"
if __name__ == "__main__":
list1 = SinglyLinkedList()
list1.add_first("MSP")
list1.add_last("ATL")
list1.add_last("BOS")
list1.remove_first()
print(list1)class Node:
def __init__(self, data):
self.data = data
self.previous = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# TO check weather list is empty or not?
def is_empty(self):
if self.head is None:
return True
else:
return False
def add_node(self, data):
# Creating New Node
newNode = Node(data)
# Checking where the head and tail pointer is pointing.
# if first node is added to the list then below condition should be true.
if self.head is None:
self.head = newNode
newNode.previous = newNode.next = None
else:
# Addding new node at the last
self.tail.next = newNode
newNode.previous = self.tail
newNode.next = None
self.tail = newNode
def display_list(self):
# Creating temp pointer to travers
temp = self.head
if temp is not None:
while temp is not None:
print(temp.data, end=" -> ")
temp = temp.next
else:
print("NULL")
else:
print("List does not have any nodes")
def clone_linked_list(l1):
dl = DoublyLinkedList()
temp = l1.head
if temp is not None:
while temp is not None:
dl.add_node(temp.data)
temp = temp.next
return dl
if __name__ == "__main__":
list1 = DoublyLinkedList()
list1.add_node("MSP")
list1.add_node("ATL")
list1.add_node("BOS")
# list1.remove_first()
print(list1.display_list())# -*- coding: utf-8 -*-
class Node:
def __init__(self, element, next_node=None):
self.element = element
self.next_node = next_node
class CircularlyLinkedList:
def __init__(self):
self.tail = None
self.size = 0
def __len__(self):
return self.size
def is_empty(self):
return self.size == 0
def first(self):
if self.is_empty():
return None
return self.tail.next_node.element
def last(self):
if self.is_empty():
return None
return self.tail.element
def rotate(self):
if self.tail is not None:
self.tail = self.tail.next_node
def add_first(self, e):
if self.is_empty():
self.tail=Node(e)
self.tail.next_node = self.tail # a new list of one element
else:
newest = Node(e)
newest.next_node = self.tail.next_node
self.tail.next_node = newest
self.size += 1
def add_last(self, e):
self.add_first(e)
self.tail = self.tail.next_node
def remove_first(self):
if self.is_empty():
return None
old_head = self.tail.next_node
if self.size == 1:
self.tail = None
else:
self.tail.next_node = old_head.next_node
self.size -= 1
return old_head.element
def __str__(self):
if self.is_empty():
return "[]"
result = []
current = self.tail.next_node
result.append(str(current.element))
current = current.next_node
while current != self.tail.next_node:
result.append(str(current.element))
current = current.next_node
return "[" + ", ".join(result) + "]"
if __name__ == "__main__":
originalList = CircularlyLinkedList()
originalList.add_last("MSP")
originalList.add_last("ATL")
originalList.add_last("BOS")
print(originalList) # Should print: [MSP, ATL, BOS]