标签: linked-list

在Java中创建链表的最佳方法是什么？

我之前在Java中广泛使用链表,但我对C++很新.我正在使用在项目中给我的这个节点类就好了

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

但我有一个问题没有得到很好的回答.为什么有必要使用

Node *m_next;

指向列表中的下一个节点而不是

Node m_next;

我知道最好使用指针版本; 我不会争论事实,但我不知道为什么它会更好.关于指针如何更好地用于内存分配,我得到了一个不太清楚的答案,我想知道这里是否有人可以帮助我更好地理解它.

我想知道是否存在一些逻辑来仅使用两个指针来反转链表.

以下用于使用三个指针(即p,q,r)反转单个链表:

struct node {
    int data;
    struct node *link;
};

void reverse() {
    struct node *p = first,
                *q = NULL,
                *r;

    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

还有其他替代方法来反转链表吗？在时间复杂度方面,逆转单链表的最佳逻辑是什么？

大多数时候,我看到人们试图使用链接列表,在我看来,这似乎是一个穷人(或非常差)的选择.也许有必要探讨链表是否是数据结构的良好选择的情况.

理想情况下,答案将阐述用于选择数据结构的标准,以及哪些数据结构在特定情况下可能最有效.

编辑:我必须说,我不仅对数字,而且对答案的质量印象深刻.我只能接受一个,但如果有一些更好的东西不存在,那么还有两三个我不得不说会值得接受.只有一对(特别是我最终接受的那个)指出了链表提供了真正优势的情况.我确实认为Steve Jessop不仅要提出一个,而且要提出三个不同的答案,值得一提,我发现这些答案令人印象深刻.当然,即使它只是作为评论发布而不是答案,我认为Neil的博客条目也值得一读 - 不仅信息丰富,而且非常有趣.

我一直在为一个类的Java项目工作.它是链表的实现(此处称为AddressList包含调用的简单节点ListNode).问题在于,所有事情都必须通过递归算法来完成.我能做的一切都很好,没有一种方法:public AddressList reverse()

ListNode:

public class ListNode{
  public String data;
  public ListNode next;
}

现在我的reverse函数只调用一个辅助函数,该函数接受一个允许递归的参数.

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

我的助手功能有签名private ListNode reverse(ListNode current).

目前,我使用堆栈迭代地工作,但这不是规范要求的.我在C中找到了一个递归反转的算法,并手工将其转换为Java代码,但是它有效,但我对此并不了解.

编辑:没关系,我在此期间弄清楚了.

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

虽然我在这里,有没有人看到这条路线有任何问题？

根据关于链表的维基百科文章,在链表中间插入被认为是O(1).我认为这将是O(n).您是否需要找到可能接近列表末尾的节点？

此分析是否不考虑节点操作的发现(虽然它是必需的)并且只是插入本身？

编辑:

链接列表与数组相比有几个优点.在列表的特定点处插入元素是恒定时间操作,而在数组中插入可能需要移动一半或更多元素.

上述陈述对我来说有点误导.如果我错了,请纠正我,但我认为结论应该是:

阵列:

• 找到插入/删除点O(1)
• 执行插入/删除O(n)

链接列表:

• 找到插入/删除点O(n)
• 执行插入/删除O(1)

我认为你唯一一次不必找到位置就是你保留了某种指针(如某些情况下的头部和尾部).因此,我们不能断然说链接列表总是超过插入/删除选项的数组.

我很好奇O(n log n)是链表最好的.

这个问题可能已经过时了,但我想不出答案.

比如,有两个不同长度的列表,在某一点合并 ; 我们怎么知道合并点在哪里？

条件:

1. 我们不知道长度
2. 我们应该只解析每个列表一次.

我们不能总是使用HashMap的原因是什么,即使它在添加,删除操作方面比ArrayList或LinkedList更有效,也与元素的数量无关.

我用Google搜索并发现了一些原因,但总是有一个使用HashMap的解决方法,优势仍然存在.

我正在为我正在进行的项目构建一个符号表.我想知道人们对可用于存储和创建符号表的各种方法的优点和缺点的看法.

我做了很多搜索,最常推荐的是二叉树或链表或哈希表.以上所有优点和缺点是什么？(在c ++中工作)