package linkedlists;
import linkedlists.DoublyLinkedList.Node;
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.
*/
public 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();
}
public DoublyLinkedList<E> concatenate(DoublyLinkedList<E> L, DoublyLinkedList<E> M) {
M.header = L.trailer;
M.trailer = L.header;
return L;
}
//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());
//
}
}
任务:在本练习中，你将使用课本(第二周讲座示例)中的DoublyLinkedList实现。编写一个方法，将两个双链表L和M(带有头节点和尾节点)连接到一个列表L '中。编写一个主方法来测试新方法。提示:把L的结尾连成m的开头
我在解决这个问题时遇到了困难，我写了这个代码
public DoublyLinkedList<E> concatenate(DoublyLinkedList<E> L, DoublyLinkedList<E> M) {
M.header = L.trailer;
M.trailer = L.header;
return L;
}
并在几个小时内对其进行了大量修改，但仍然无法得到它是什么。有人能帮忙吗?
主要
DoublyLinkedList<String> list1 = new DoublyLinkedList<String>();
list1.addFirst("A");
list1.addLast("B");
list1.addLast("C");
list1.addLast("D");
DoublyLinkedList<String> list2 = new DoublyLinkedList<String>();
list2.addFirst("1");
list2.addLast("2");
list2.addLast("3");
list2.addLast("4");
list1.concatenate(list2);
System.out.println(list1);
分析
- 哨兵节点用于
header和trailer - 总有
4哨点 - 合并后应该只有
2哨兵节点
ListL
headerL -> NodeL1 -> NodeL2 -> trailerL -> headerL
trailerL <- headerL <- NodeL1 <- NodeL2 <- trailerL
ListM
headerM -> NodeM1 -> NodeM2 -> trailerM -> headerM
trailerM <- headerM <- NodeM1 <- NodeM2 <- trailerM
预期结果headerL -> NodeL1 -> NodeL2 -> NodeM1 -> NodeM2 -> trailerM -> headerL
trailerM <- headerL <- NodeL1 <- NodeL2 <- NodeM1 <- NodeM2 <- trailerM
代码中的问题
public DoublyLinkedList<E> concatenate(DoublyLinkedList<E> L,
DoublyLinkedList<E> M) {
M.header = L.trailer;
M.trailer = L.header;
return L;
}
更新M.header和M.trailer没有帮助，因为它只是重新分配哨兵节点。
方法- 头。接下来,头。上一页,拖车。接下来,拖车。以下是变更的主要候选项
- header.next。prev、tailor .prev.next是其他需要更新的候选文件。
- 在这些情况下，最好附加第一个列表和第二个列表(trailerL将与headerM连接)
- 在headerL和trailerM之间创建引用
- 删除trailerL
- 删除headerM
// join trail of first list with head of second list
Node trailerL = L.trailer;
Node headerM = M.header;
L.trailer.setNext(M.header);
M.header.setPrev(L.trailer);
// join head of first list with tail of second list
// this will be header and trailer of the merged list
L.header.setPrev(M.trailer);
M.trailer.setNext(L.header);
L.size += 2;
// delete trailerL and headerM
remove(trailerL);
remove(headerM);
在DoublyLinkedList类中试试这个方法
public void concatenate(final DoublyLinkedList<E> other) {
final Node trailerL = this.trailer;
final Node headerM = other.header;
this.trailer.setNext(other.header);
other.header.setPrev(this.trailer);
this.header.setPrev(other.trailer);
other.trailer.setNext(this.header);
this.size += 2;
this.remove(trailerL);
this.remove(headerM);
}