Linked list

叶归叶

最近在学着linked list...不过不是很明白
希望有谁了解的可以讲解一下...感激不尽
比如说,
1.怎样存user input into the linked list?跟array 一样吗?(用for loop?)
2.怎样get user input from the linked list? 比方说一直用link->next而已吗?
3.How to declare linked list?这样吗?
struct LinkedList
{
int num;
INTEGER *headPtr;
};
typedef struct LinkedList LIST;
那malloc又是做麽的?

onlylonly

你必需先明白 linked list 的操作。。。

linked list 是将所有的节点（nodes）连接起来， 也就是为什么叫做linked。。

一个节点的delaration应该是
struct LinkedList
{
<datatype> item;
LinkedList *next;
};

若是c++的话， 可用template

template <typename T>
struct LinkedList
{
T item;
LinkedList *next;
};

或是要加入constructor
template <typename T>
class LinkedList
{
public:
LinkedList();
LinkedList(T item, LinkedList *next = 0 )
{
     this->item = item;
     this->next = next;
}
T item;
LinkedList *next;
};

你的资料将存于每一个节点中的 item data member / variable, 而用来连接节点的地址将存于 *next；

yeenfei

原帖由 叶归叶 于 28-2-2009 08:47 PM 发表
最近在学着linked list...不过不是很明白 &#160;
希望有谁了解的可以讲解一下...感激不尽
比如说,
1.怎样存user input into the linked list?跟array 一样吗?(用for loop?)
2.怎样get user input from the linked list? 比方说一直用link->next而已吗?
3.How to declare linked list?这样吗?
struct LinkedList
{
int num;
INTEGER *headPtr;
};
typedef struct LinkedList LIST;
那malloc又是做麽的?

首先必须明白pointer (指针）的概念 -如&#160; Deferencing(*), AddressOf(&)
这是基础知识，我不多讲，自己看书参考

然后知道如何在运行时（runtime）创建（create)物件（object) :

你可以用new这个operator来完成；或者
用malloc来分离（allocate）一部分记忆体(memory)储存你的新物件

问题1 - 将新物件加入linked list :
不能跟array一样，原因： 1.）你可能不知道到底linked list有多大; 2.)在电脑记忆体里，每个物件的储存位置排列并不连贯(contiguous)
正确方法为：
1.) linked list里每个物件应该有一个variable来记载下一个物件的存放位置；
2.) linked list 里的最后一个物件不会记录下一个存放位置，所以该variable 要指去0 (代表不存在);
3.) 创建一个新的物件,然后将它的存放位置写进linked list的最后一个node的variable

问题2) 怎样游览 linked list?

比方说一直用link->next而已吗?

next只不过是我们自创的function罢了， 掌握pointer后你会明白。。。

问题3) 怎样设立 linked list?
严格来讲, linked list 是很抽象(abstract)的，也只不过是一种记忆体储存物件的概念；
它可以简单到只是指去第一个物件/node 的pointer

[ 本帖最后由 yeenfei 于 1-3-2009 11:23 PM 编辑 ]

叶归叶

非常谢谢两位...虽然还不是很明白 不过比之前好很多了...
我会继续研究不明白再来请教两位

原帖由 yeenfei 于 1-3-2009 06:59 PM 发表
2.) linked list 里的最后一个物件不会记录下一个存放位置，所以该variable 要指去0 (代表不存在);
...

代表不存在...是要指去0还是NULL?

yeenfei

原帖由 叶归叶 于 2-3-2009 08:35 PM 发表
非常谢谢两位...虽然还不是很明白 不过比之前好很多了...
我会继续研究不明白再来请教两位
代表不存在...是要指去0还是NULL?

NULL就是0啊。。

onlylonly

O 为节点 （ node ）
--- 为连接 （ link ）

   O ---- O ---- O ----- O
head                         tail

基本上， linked list 的操作如上图。。 以不同不同的节点，全部连接起来， 成为一个linked list 。

放大后的解构为：
-------------                                   -------------
|  DATA   |                ------------>  |  DATA   |
-------------                |                  -------------
|  NEXT   | ------------|                  |  NEXT   |
-------------                                   -------------

DATA - 存放资料， 可以是int ，double， char， string， 甚至是一个object （ OOP 里面的时候）， 可以是任何东西。
如果是 linklist.push_back('a');
那么， data 就是 a

NEXT 是指向另一个node 的地址

守护神亚罗斯

LINKED LIST的重点在于，PREVIOUS 和NEXT

叶归叶

原帖由 yeenfei 于 2-3-2009 09:23 PM 发表


NULL就是0啊。。

不好意思...跟database搞混了

叶归叶

我今天终于弄明白linked list了...现在要开始学用linked list写program...
真的很谢谢大家