在链表的单个索引中存储 1 个以上的数据项? [英] Storing more than 1 data item at a single index in a linked-list?

问题描述

我试图在我的链接列表的单个索引中存储 1 个以上的数据项.我教科书中的所有示例似乎都说明了每个索引仅添加 1 条数据.我假设可以添加更多?

I am trying to store more than 1 data item at a single index in my linked-list. All of the examples in my textbook seem to illustrate adding only 1 piece of data per index. I'm assuming it is possible to add more?

例如，使用 Collections API 来存储整数，我会执行以下操作:

For example, using the Collections API to store an integer I would do the following:

LinkedList <Integer>linky = new LinkedList<Integer>();
int num1 = 2, num2 = 22, num3 = 25, num4 = 1337;
linky.add(num1);

我将如何将 num2、num3 和 num4 添加到列表中相同的第一个索引?多谢你们.

How would I go about adding num2, num3, and num4 to the same first index in the list? Thanks guys.

推荐答案

关于链表的工作方式似乎有些混乱.本质上，链表由节点组成，每个节点包含一个数据(一个对象，准确地说，它本身可以包含多个成员变量)和一个到链表中下一个节点的链接(或者一个空指针，如果有的话)没有这样的下一个节点).你也可以有一个双向链表，其中每个节点还有一个指向列表中前一个节点的指针，以加快某些类型的访问模式.

There seems to be a little confusion about how linked lists work. Essentially, a linked list is composed of nodes, each of which contains one datum (an object, which itself can contain several member variables, to be precise), and a link to the next node in the list (or a null pointer if there is no such next node). You can also have a doubly-linked list, where each node also has a pointer to the previous node in the list, to speed up certain kinds of access patterns.

将多个数据片段"添加到单个节点听起来就像从一个节点添加多个链接，这会将您的链表变成 N 叉 树.

To add multiple "pieces of data" to a single node sounds like adding several links off of one node, which turns your linked list into an N-ary tree.

要将多条数据添加到列表的末尾，以最常与链表关联的方式，只需执行以下操作:

To add multiple pieces of data onto the end of the list, in the manner most commonly associated with a linked list, just do:

LinkedList <Integer>linky = new LinkedList<Integer>();
int num1 = 2, num2 = 22, num3 = 25, num4 = 1337;
linky.add(num1);
linky.add(num2);
linky.add(num3);
linky.add(num4);

或者，如果你想让链表的每个节点有几条数据

这些数据应该打包成一个对象(通过定义一个class，将它们都作为成员变量).例如:

Alternately, if you want each node of the linked list to have several pieces of data

These data should be packaged up into an object (by defining a class that has them all as member variables). For example:

class GroupOfFourInts
{
   int myInt1;
   int myInt2;
   int myInt3;
   int myInt4;

   public GroupOfFourInts(int a, int b, int c, int d)
   {
     myInt1 = a; myInt2 = b; myInt3 = c; myInt4 = d;
   }
}

class someOtherClass
{

  public static void main(String[] args)
  {
    LinkedList<GroupOfFourInts> linky = new LinkedList<GroupOfFourInts>();
    GroupOfFourInts group1 = new GroupOfFourInts(1,2,3,4);
    GroupOfFourInts group2 = new GroupOfFourInts(1337,7331,2345,6789);
    linky.add(group1);
    linky.add(group2);
  }
}

现在，linky 将有 2 个节点，每个节点将包含 4 个 ints、myInt1、myInt2、myInt3 和 myInt4.

Now, linky will have 2 nodes, each of which will contain 4 ints, myInt1, myInt2, myInt3, and myInt4.

以上都不是特定于链表的.每当您想将一堆数据作为一个单元存储在一起时，就应该使用这种模式.您创建一个类，该类具有要存储在一起的每条数据的成员变量，然后创建该类型的任何 Java 集合类型(ArrayList、LinkedList、TreeList 等).

None of the above is specific to linked lists. This pattern should be used whenever you want to store a bunch of data together as a unit. You create a class that has member variables for every piece of data you want to be stored together, then create any Java Collections type (ArrayList, LinkedList, TreeList, ...) of that type.

确保您要使用链表(因为在选择 ArrayList 或 TreeList 时不会因为编程难度而受到惩罚).这将取决于您的数据访问模式.链表提供 O(1) 次添加和删除，但 O(n) 查找，而 ArrayLists 提供 O(1) 次查找，但 O(n) 任意添加和删除.TreeLists 提供 O(log n) 的插入、删除和查找.这些之间的权衡取决于您拥有的数据量以及您将如何修改和访问数据结构.

Be sure that you want to use a linked list (as there's no penalty in terms of programming difficulty in choosing an ArrayList or TreeList). This will depend on your data access pattern. Linked lists provide O(1) addition and deletion, but O(n) lookup, whereas ArrayLists provide O(1) lookup, but O(n) arbitrary add and delete. TreeLists provide O(log n) insertion, deletion, and lookup. The tradeoffs between these depend on the amount of data you have and how you're going to be modifying and accessing the data structure.

当然，如果您的列表中只有 <100 个元素；-)

Of course, none of this matters if you'll only have, say, <100 elements in your list ;-)

希望这有帮助！

这篇关于在链表的单个索引中存储 1 个以上的数据项?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！