Связанные списки без импорта

Question

Я пытаюсь создать связанный список, двойной или одиночный, без использования импорта, это часть проекта класса.но я не понимаю, я думаю, как на самом деле создать и добавить элемент в список, без использования java.util.У меня есть

public boolean insertItem( ItemType newItem)
{
    if( p==0 || m==MAX_LENGTH)
    {
        head.elem = elem;
        head.next = tail; 
        tail = head;
        return false;
    } 
    else
    {
        tail.next = new ListNode(); //adds new node to the end of the list
        tail = tail.next;//set the tail pointer to that node
        tail.elem = newItem;  //set elem to be stored to the end node
        m++;
        return true;
    }
}

, поэтому я хотел бы узнать, почему это не работает.и как я на самом деле создал этот список, я использовал массив только Object list[] = new list[MAX_LENGTH], но я не уверен, что это правильный путь.

Answer 1

Я бы начал с чего-то вроде:

class LinkedList
{
    static class Node
    {
         ItemType item;
         Node next;
         Node prev; // if making a doubly linked list
    }

    private Node head;
    private Node tail; // if making a doubly linked list

    public boolean insertItem(ItemType item)
    {   
        // make a new Node         
        // check for the head to be null...
        // add the node to the end of the list, or make the head/tail point at it.
    }
}

Answer 2

И нет, это неправильный путь .

См. Википедия: Связанный список - это структура данных, к которой призывает это назначение.Каждая ячейка имеет значение и «указатель» на следующую (и, возможно, предыдущую).

Не использовать массивы - структура списка автономна в ячейках и ссылках.

Рассмотрите эту подпись, чтобы добавить новый элемент: (Как только базовая операция понята / реализована, ее можно легко превратить в метод.)

static LinkedList insert(LinkedList item, LinkedList newItem) {
   // Update item to "point to" newItem and have newItem "point to" where
   // item used to "point to". Return the new "head" of this
   // segment.

   // Notes:
   // `item` may be null to "insert at start of empty list"
   // This function should be *static* and should only modify
   // item and newItem.
}

Примеры использования:

LinkedList head = insert(null, new LinkedList("a"));
insert(head, new LinkedList("b"));
length(head); // should be 2, cons cells should look like `("a", ("b", null))`
insert(head, new LinkedList("c"));
length(head); // should be 3, cons cells should look like `("a", ("c", ("b", null)))`

Помните, что объект LinkedList выше относится к одной «ячейке» с двумя (или тремя) членами: «значение», «следующий» (и, необязательно, «предыдущий»).В зависимости от предпочтений и т. Д. Node или Cell может быть более подходящим именем, чтобы оставить LinkedList для обозначения стандартной коллекции и / или внешнего контейнера.

Удачная домашняя работа.

---

Примечание: LinkedList в API коллекции Java - это контейнер, который использует связанный список в качестве базовой реализации.Как таковой, он упускает из числа хороших вариантов использования связанных списков, часто используемых в языках программирования с функциональным заголовком.