Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
6th Edition
ISBN: 9781118771334
Author: Michael T. Goodrich
Publisher: WILEY
Expert Solution & Answer
Book Icon
Chapter 3, Problem 31C

Explanation of Solution

Reimplementation of DoublyLinkedList class using only one sentinel node:

The doubly linked list is a linked data structure which contains the collection of sequentially data with two sentinel nodes such as “header” and “trailer”.

  • If there is only one sentinel node, then the list is circularly linked using sentinel node.
  • That is, header is sentinel node means, the next of the header is first node of list and previous node of header is last node of list.

Code for DoublyLinkedList class using only one sentinel node:

//Define the DoublyLinkedList class

public class DoublyLinkedList<E>

{

  //Declare only one sentinel node

private Node<E> header;

  //Declare and initialize the "size" variable

private int size = 0;

/*Define the Constructor to construct a new empty list. */

  public DoublyLinkedList()

  {

//Create header sentinel

header = new Node<>(null, null, null);

  }

//Define the size() method

  public int size()

  {

/*Returns the number of elements in the linked list. */

  return size;

  }

  //Define isEmpty() method

  public boolean isEmpty()

  {

  //Check whether the linked list is empty

  return size == 0;

  }

//Define first() method

  public E first()

  {

  //Check whether the list is empty

  if(isEmpty())

  //Return null

  return null;

//Returns the first element of the list

  return header.getNext().getElement();

  }

//Define last() method

  public E last( )

  {

  //Check whether the list is empty

  if(isEmpty())

  //Return null

  return null;

/*Returns the last element of the list using the single sentinel node "header". */

  return header.getPrev().getElement( );

  }

  //Define addFirst() method

  public void addFirst(E e)

  {

/*Call addBetween() method to adds element "e" to the front of the list. */

  addBetween(e, header, header.getNext

  }

  /Define the addLast() method

  public void addLast(E e)

  {

/*Call addBetween() method to adds element e to the end of the list using single sentinel node "header". */

  addBetween(e, header.getPrev(), header);

  }

//Define the removeFirst() method

  public E removeFirst()

  {

  //Check whether the list is empty

  if (isEmpty())

  //Return null

  return null;

/*Call remove() method to removes and returns the first element of the list. */

  return remove(header...

Blurred answer
Students have asked these similar questions
Java Programming language Please help me with this. Thanks in advance.
Important: Make all your implementation in the same attached file and submit only one file in the submission link. Given the linked list data structure discussed in the lecture, implement a sub-class TSortedList that makes sure that elements are inserted and maintained in an ascending order in the list. So, given the input sequence {1,7,3,11,5}, when printing the list after inserting the last element it should print like 1, 3, 5, 7, 11. Note that with inheritance, you have to only care about the insertion situation as deletion should still be handled by the parent class. In the basic implementation, assume that you only have head which is a pointer to the head of the list. Now, if we have both head and tail pointers, what improvements can be done to speed up the insertion?
You may find a doubly-linked list implementation below. Our first class is Node which we can make a new node with a given element. Its constructor also includes previous node reference prev and next node reference next. We have another class called DoublyLinkedList which has start_node attribute in its constructor as well as the methods such as: 1. insert_to_empty_list() 2. insert_to_end() 3. insert_at_index() Hints: Make a node object for the new element. Check if the index >= 0.If index is 0, make new node as head; else, make a temp node and iterate to the node previous to the index.If the previous node is not null, adjust the prev and next references. Print a message when the previous node is null. 4. delete_at_start() 5. delete_at_end() . 6. display() the task is to implement these 3 methods: insert_at_index(), delete_at_end(), display(). hint on how to start thee code # Initialize the Node class Node:             def __init__(self, data):                      self.item = data…
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education