Блог

Я пытаюсь реализовать список с двойной круговой связью и немного заблудился; у меня есть свой список с двойной связью, но я не совсем уверен в том, как сделать его круговым. Я прочитал, что только последний узел указывает на первый узел, так что это будет что-то вроде:

 public void addLast(DNode v) {
addAfter(header, v);

}
  

Вот код для моего дважды связанного списка:

 public class Dlist {

protected int size;
protected DNode header, trailer;

public Dlist() {
    size = 0;
    header = new DNode(null, null, null);
    trailer = new DNode(null, header, null);
    header.setNext(trailer);

}//end DList()

public int size() { return size; }

public boolean isEmpty() { return (size == 0); }


public DNode getFirst() throws IllegalStateException {
    if (isEmpty()) throw new IllegalStateException("List is empty");
    return header.getNext();
}//end isEmpty


public DNode getLast() throws IllegalStateException {
    if (isEmpty()) throw new IllegalStateException("List is empty");
    return trailer.getPrev();

}//end getLast


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();
}


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();
}

public void addBefore(DNode v, DNode z) {
    DNode u = getPrev(v);
    z.setPrev(u);
    z.setNext(v);
    v.setPrev(z);
    u.setNext(z);
    size  ;

}

public void addAfter(DNode v, DNode z) {
    DNode w = getNext(v);
    z.setPrev(v);
    z.setNext(w);
    w.setPrev(z);
    v.setNext(z);
    size  ;
}

public void addFirst(DNode v) {
    addAfter(header, v);
}

public void addLast(DNode v) {
    addBefore(trailer, v);

}

public void remove(DNode v) {
    DNode u = getPrev(v);
    DNode w = getNext(v);

    w.setPrev(u);
    u.setNext(w);
    v.setPrev(null);
    v.setNext(null);
    size--;

}

public boolean hasPrev(DNode v) { return v != header;}

public boolean hasNext(DNode v) { return v != trailer; }

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;
    }
    return s;
}
  

РЕДАКТИРОВАТЬ: DNode;

 public class DNode {
protected String element;
protected DNode next, prev;

public DNode(String e, DNode p, DNode n) {
    element = e;
    prev = p;
    next = n;

}

public String getElement() {return element;}

public DNode getPrev() { return prev; }

public DNode getNext() { return next; }

public void setElement(String newElem) { element = newElem; }

public void setPrev(DNode newPrev) { prev = newPrev; }

public void setNext(DNode newNext) {next = newNext;}
}
  

Теперь у вас есть header и trailer псевдо-узел:

 header <--> first <--> second <--> ... <--> last <--> trailer
  

Вместо этого вам пришлось бы соединить первый и последний в обоих направлениях.

         .-> first  <--> second <--> ... <--> last <-.
        |                                           |
        '-------------------------------------------'
  

В качестве альтернативы вы также можете объединить заголовок и трейлер в одном узле, но тогда это не будет «чистым» списком с круговой связью, поскольку при обходе вам придется перешагивать через узел заголовка / трейлера.

         .-> first  <--> second <--> ... <--> last <--> header/trailer <-.
        |                                                               |
        '---------------------------------------------------------------'
  

Циклический список не имеет заголовка, трейлера, первого или последнего элемента. Это накладывает на вас особые требования.

У вас может быть либо псевдоэлемент, либо нет.

Если у вас есть псевдоэлемент, то вам нужно обрабатывать его как особый случай в getNext и getPrevious , поскольку он должен быть пропущен, но вам не нужно беспокоиться о том, что произойдет, когда список пуст или если вы удаляете что-то важное.

Если у вас нет псевдоэлемента, то нет особых случаев для next и previous, но есть особый случай для add, когда список пуст, и remove, если вы удаляете узел, с помощью которого вы связываетесь со списком.