在链表中的单个索引处存储多个数据项？

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?

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

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

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

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.

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

6 个解决方案

#1

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.

将多个“数据片段”添加到单个节点听起来像是从一个节点添加多个链接,这会将链接列表转换为N-ary树。

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.

现在,linky将有2个节点,每个节点将包含4个整数,myInt1,myInt2,myInt3和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.

以上都不是链接列表特有的。只要您想将一堆数据作为一个整体存储在一起,就应该使用此模式。您创建一个类,其中包含要存储在一起的每个数据的成员变量,然后创建该类型的任何Java集合类型(ArrayList,LinkedList,TreeList,...)。

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.

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

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

当然,如果您的列表中只有<100个元素,那么这一切都不重要;-)

Hope this helps!

希望这可以帮助!

#2

Use a structure.

使用结构。

For example:

private struct Node
{
    int Num1;
    int Num2;
    int Num3;
}

...

LinkedList<Node> list = new LnkedList<Node>();

Node n = new Node();
n.Num1 = 10;
n.Num2 = 100;
n.Num3 = 1000;
list.Add(n);

Note; I assume this is in C#; correct me if I'm wrong and I will fix the code ;)

注意;我认为这是在C#中;如果我错了,请纠正我,我会修复代码;)

If you have not gone over OOP yet in your book - then I would recommend giving it a try; it will help you solve problems like this.

如果你还没有在你的书中找到OOP - 那么我会建议试一试;它会帮助你解决这样的问题。

#3

Why not something like that:

为什么不是这样的:

LinkedList<LinkedList<Integer>> linky = new LinkedList<LinkedList<Integer>>();
//...
linky.add(new LinkedList<Integer>().add( //...

#4

Like Nelson said you need another Object, in Java though you need to use a Class. If you need the 'Node' Class to be used outside the Class you're working in, then you need to make it a Public class, and move it to it's own file.

就像Nelson说你需要另一个Object,在Java中你需要使用一个Class。如果您需要在您正在使用的类之外​​使用'Node'类,那么您需要将其设置为Public类,并将其移动到它自己的文件中。

private Class Node
{
    //You might want to make these private, and make setters and getters
    public int Num1;
    public int Num2;
    puclic int Num3;
}

LinkedList<Node> list = new LinkedList<Node>();

Node n = new Node();
n.Num1 = 10;
n.Num2 = 100;
n.Num3 = 1000;
list.Add(n);

Apologies to Nelson for stealing his code ;)

向尼尔森道歉,因为他偷了他的代码;)

#5

Here's a complete code sample that shows the use of adding a structure to a linked list:

这是一个完整的代码示例,显示了将结构添加到链表的用法:

import java.util.LinkedList;
class Node {
    int num1;
    int num2;
    int num3;
    int num4;
    public Node(int a, int b, int c, int d) {
        num1 = a; num2 = b; num3 = c; num4 = d;
    }
}
public class dummy {
    public static void main(String[] args) {
        LinkedList <Node>linky = new LinkedList<Node>();
        x myNode = new Node(2, 22, 25, 1337);
        linky.add(myNode);
    }
}

#6

I don't really understand what you are trying to achieve, so I suggest a solution to another reading of the problem (in java).

我真的不明白你想要实现什么,所以我建议另一个解决问题的解决方案(在java中)。

LinkedList <Integer>linky = new LinkedList<Integer>();
linky.add(num1);

// Lots of code possibly adding elements somewhere else in the list

if (linky.size() > 0) { // Always good to be sure; especially if this is in another methode
 int first = linky.get(0);
 linky.set(0, first + num2);// Value of linky.get(0) is num1 + num2 
}


// The same again
// Lots of code possibly adding elements somewhere else in the list

if (linky.size() > 0) { // Always good to be sure; especially if this is in another methode
 int first = linky.get(0);
 linky.set(0, first + num3); // Value of linky.get(0) is num1 + num2 + num3
}

I personally happen to like Nelson's solution best if the amount of numbers to add is constant (num1 .. num4), and if it is not constant I would prefer Gregor's solution (who uses a List in stead of a Node). If you go for the Node method in java I suggest:

如果要添加的数量是恒定的(num1 .. num4),我个人碰巧最喜欢Nelson的解决方案,如果它不是常数我宁愿Gregor的解决方案(谁使用List而不是Node)。如果你在java中使用Node方法我建议:

// added static, Class to class
private static class Node
{
    //You might want to make these private, and make setters and getters
    public int Num1;
    public int Num2;
    puclic int Num3;
}

// Prefer interfaces if possible
List<Node> list = new LinkedList<Node>();

Node n = new Node();
n.Num1 = 10;
n.Num2 = 100;
n.Num3 = 1000;
list.add(n); // Add -> add

Lot's of nitpicking, but I think a static class in stead of a none-static private class is preferred if possible (and it normally should be possible).

很多人都在挑剔,但我认为如果可能的话,首选静态类而不是非静态私有类(并且通常应该是可能的)。