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

问题描述

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

例如，使用Collections API存储整数，我将执行以下操作：

  LinkedList< Integer> linky = new LinkedList< Integer>（）; 
 int num1 = 2，num2 = 22，num3 = 25，num4 = 1337; 
 linky.add（num1）; 
  

如何将num2，num3和num4添加到列表中的第一个索引？多谢你们。

解决方案

关于链表如何工作，似乎有些混乱。基本上，链表由多个节点组成，每个节点包含一个数据（一个对象，其本身可以包含多个成员变量），以及指向列表中下一个节点的链接（如果有一个空指针是没有这样的下一个节点）。您还可以有一个双向链表，其中每个节点还有一个指向列表中上一个节点的指针，以加快某些种类的访问模式。

向单个节点添加多个数据片段听起来像添加了一个节点的几个链接，这将您的链接列表转换为N元树。

要以列表最常用的方式将多个数据添加到列表的末尾，只需执行：

  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 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 int s， myInt1 ， myInt2 。 以上都不是特定于链接列表。每当你想将一堆数据作为一个单元存储在一起时，应该使用这个模式。您创建一个类，其中包含要存储在一起的每个数据的成员变量，然后创建该类型的任何Java集合类型（ArrayList，LinkedList，TreeList，...）。

确保您要使用链表（因为在选择ArrayList或TreeList时在编程难度方面没有损失）。这将取决于您的数据访问模式。链接列表提供O（1）添加和删除，但O（n）查找，而ArrayLists提供O（1）查找，但O（n）任意添加和删除。树列表提供O（log n）插入，删除和查找。这些之间的权衡取决于你拥有的数据量，以及你将如何修改和访问数据结构。

当然，这些都不重要，如果您只会在列表中包含&​​lt; 100元素; - ）

希望这有助于！

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?

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

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.

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

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

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

Note

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.

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.

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

Hope this helps!

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