Как написать базовые функции двойного связного списка в Java?

Question

Мое первое задание в моем классе программирования касается написания кода для Doubly Linked List, который включает в себя запись добавления, удаления, размера, итератора, итератора last и функции поиска итератора. Я провел 3 часа и не понял, где это понимать. Я понимаю, что произойдет, если я увижу это на картинке. Но моя проблема заключается в переводе кода на код. Это то, что у меня есть до сих пор:

public class DoublyLinkedList<G> { 

    public class node { 
     G data; 
     node next; 
     node prev; 
     public node(G data, node next, node prev) { 
      this.data = data; 
      this.next = next; 
      this.prev = prev; 
     } 
    } 
    node header; 
    node footer; 


    public DoublyLinkedList() { 
     header = new node(null, null, null); 
     footer = new node(null, header, null); 
     header.next = footer; 
    } 

    public void add(G data) { 
     header.next = new node(data, footer.prev, footer); 
    } 

    public int size() { 
     node current = header.next; 
     int quanity = 0; 
     if (current == null) { 
      return 0; 
     } 
     while (current != null) { 
      current = current.next; 
      quanity++; 
     } 
     return quanity; 
    } 

    public static void main(String args[]) { 

     DoublyLinkedList<Integer> test = new DoublyLinkedList<Integer>(); 
     //test.add(new Integer(2)); 
     //test.add(new Integer(22)); 
     //test.add(new Integer(222)); 

      System.out.println(test.size()); 

    } 
} 

Как вы можете видеть, я использую main() для проверки всего. Из того, что мне сказал мой учитель, мой конструктор и класс узлов выглядят отлично. Тем не менее, я знаю, что либо добавление, либо размер не являются правильными, потому что, когда я проверяю это, когда в списке нет узлов, он ничего не отображает, но он должен показывать 0 правильно? Я имею в виду, если предположить, что мой код размера прав, и я не уверен.

И всякий раз, когда я добавляю узел, независимо от того, сколько я добавляю, он всегда отображает 1. Таким образом, либо как добавление, либо размер разбиты, либо оба. Я не писал других функций, поскольку это не имеет никакого смысла, пока я не выберу их. Пожалуйста, помогите мне понять это! Спасибо.

Answer 1

Здесь вы идете:

public class DoublyLinkedList { 
private class Node { 
    String value; 
    Node next,prev; 

    public Node(String val, Node n, Node p) { 
     value = val; 
     next = n; 
     prev=p; 
    } 

    Node(String val) { 
     this(val, null, null); 
    } 
} 
private Node first; 
private Node last; 

public DoublyLinkedList() { 
    first = null; 
    last = null; 
} 
public boolean isEmpty(){ 
    return first==null; 
} 
public int size(){ 
    int count=0; 
    Node p=first; 
    while(p!=null){ 
     count++; 
     p=p.next; 
    } 
    return count; 
} 
public void add(String e) { 

    if(isEmpty()){ 
     last=new Node(e); 
     first=last; 
    } 
    else{ 
     last.next=new Node(e, null, last); 
     last=last.next; 
    } 
} 
public void add(int index, String e){ 
    if(index<0||index>size()){ 
     String message=String.valueOf(index); 
     throw new IndexOutOfBoundsException(message); 
    } 
    if(index==0){ 
     Node p=first; 
     first=new Node(e,p,null); 
     if(p!=null) 
      p.prev=first; 
     if(last==null) 
      last=first; 
     return; 
    } 
    Node pred=first; 
    for(int k=1; k<=index-1;k++){ 
     pred=pred.next; 
    } 
    Node succ=pred.next; 
    Node middle=new Node(e,succ,pred); 
    pred.next=middle; 
    if(succ==null) 
     last=middle; 
    else 
     succ.prev=middle; 
} 
public String toString(){ 
    StringBuilder strBuilder=new StringBuilder(); 
    Node p=first; 
    while(p!=null){ 
     strBuilder.append(p.value+"\n"); 
     p=p.next; 
    } 
    return strBuilder.toString(); 
} 
public String remove(int index){ 
    if(index<0||index>=size()){ 
     String message=String.valueOf(index); 
     throw new IndexOutOfBoundsException(message); 
    } 
    Node target=first; 
    for(int k=1; k<=index;k++){ 
     target=target.next; 
    } 
    String element=target.value; 
    Node pred=target.prev; 
    Node succ=target.next; 
    if(pred==null) 
     first=succ; 
    else 
     pred.next=succ; 
    if(succ==null) 
     last=pred; 
    else 
     succ.prev=pred; 
    return element; 
} 
public boolean remove(String element){ 
    if(isEmpty()) 
     return false; 
    Node target=first; 
    while(target!=null&&!element.equals(target.value)) 
     target=target.next; 
    if(target==null) 
     return false; 
    Node pred=target.prev; 
    Node succ=target.next; 
    if(pred==null) 
     first=succ; 
    else 
     pred.next=succ; 
    if(succ==null) 
     last=pred; 
    else 
     succ.prev=pred; 
    return true; 
} 
public static void main(String[] args){ 
    DoublyLinkedList list1=new DoublyLinkedList(); 
    String[] array={"a","c","e","f"}; 
    for(int i=0; i<array.length; i++){ 
     list1.add(array[i]); 
    } 
    list1.add(1,"b"); 
    list1.add(3,"d"); 
    System.out.println(list1); 

} 


} 

Answer 2

Объявите size поле в DoublyLinkedList, чтобы сохранить текущий размер списка. Когда add преуспеть, сделайте size++. Когда remove преуспеть, сделайте size--. И метод size() просто просто возвращает значение size.

Пример кода здесь:

private int size = 0; 

    public void add(G data) { 
     header.next = new node(data, footer.prev, footer); 
     size++; 
    } 
    public int size() { 
     return size; 
    } 

Answer 3

Заметили пару вещей:

Во-первых, сноска не построен правильно. Это должно быть:

public DoublyLinkedList() { 
    .. 
    footer = new node(null, null, header); 
    // your code is incorrectly creating a circular list 
    .. 
    } 

Во-вторых, метод add() выглядит неправильно. Это должно быть что-то вроде:

public void add(G data) { 
    Node newNode = new Node(data, header, null); 
    header.prev = newNode 
    header = newNode; 
} 

// для добавления на передней панели (ЛИФО)

ИЛИ

public void add(G data) { 
    Node newNode = new Node(data, null, footer); 
    footer.next = newNode 
    footer = newNode; 
} 

// для добавления в хвосте (FIFO)

Answer 4

Проверить из wikipedia entry for doubly linked lists. У него есть хороший псевдокод.

Используя свой собственный код, который я собираюсь сделать несколько предложений

public class DoublyLinkedList<G> { 

    public class node { 
    G data; 
    node next; 
    node prev; 
    public node(G data) { 
     this.data = data; 
     this.next = null; 
     this.prev = null; 
    } 
    } 
    node header; 
    node footer; 


    public DoublyLinkedList() { 
    header = new node(null); 
    footer = new node(null); 
    header.next = footer;//link the header to the footer 
    footer.prev = header;//link the footer to the header 
    } 

    public void add(G data) { //assuming you are adding the node to the head of the list 
    node newNode = new node(data); //creating new node to add with the data 
    newNode.next = header.next; // setting new node to head of the list or the footer 
    newNode.prev = header; //setting the new node's previous node to the header 
    header.next = newNode; //setting the newNode as the next node. 
    } 

    public int size() { 
    node current = header.next; 
    int quantity = 0; 
    if (current.data == null/*Empty list*/) { //you needed to specify what you were trying to test 
     return 0; 
    } 
    while (current.data != null/*traversing the list*/) { 
     current = current.next; 
     quantity++; 
    } 
    return quantity; 
    } 

    public static void main(String args[]) { 

    DoublyLinkedList<Integer> test = new DoublyLinkedList<Integer>(); 
    //test.add(new Integer(2)); 
    //test.add(new Integer(22)); 
    //test.add(new Integer(222)); 

     System.out.println(test.size()); 

    } 
}