没有导入的链表

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对象引用了一个具有两个(或三个)成员的"单元格":"值"，"下一个"(以及可选的"prev")。根据偏好等，Node或Cell可能是一个更合适的名称，以使LinkedList指代标准集合和/或外部容器。

快乐在家办公。

---

注意:Java集合API中的LinkedList是一个使用链表作为底层实现的容器。因此，它错过了函数式编程语言中经常使用的链接列表的许多很好的用例。