Linked- List

莲花

请教linked- list 的教学方法~ 根本不能明白书上写的是什么！
求教~~

天魔神

linked list 有很多种啊，问题再具体一些 ，不然帮不到。不过先说好，我不是很PRO的PROGRAMMER，就我用过的就帮而已，分享经验
Linked list其中一个例子就好像排队那样，你安排人（就是DATA）队伍的次序，谁排在最前，谁排在最后，谁可以插队等。
它跟ARRAY有点相似，但它比较FLEXIBLE

求救孤星

哇，早已抛诸脑后。
楼主一定是学生。

莲花

天魔神 发表于 22-3-2013 09:55 AM
linked list 有很多种啊，问题再具体一些 ，不然帮不到。不过先说好，我不是很PRO的PROGRAMMER，就我用过的 ...

quene, 是什么来的？ 我读data structure 有读到这个~~

歩む

dynamic的array来的，没什么特别的。

莲花

歩む 发表于 9-4-2013 06:55 PM
dynamic的array来的，没什么特别的。

它是怎样的？可以给我一个concept它是什么吗？

歩む

莲花 发表于 9-4-2013 07:14 PM
它是怎样的？可以给我一个concept它是什么吗？

用讲的你可能比较难理解诶……
我现在不在公司，电脑只有eclipse，我用Java写个sample给你看好吗？

歩む

莲花 发表于 9-4-2013 07:14 PM
它是怎样的？可以给我一个concept它是什么吗？

先跟你讲基本的东西先。
Linked List是一种Data Structure，说它是dynamic的arrays也是有点不对。
这种data structure用来保存一整个队列的data，但不是通过index来存取data，而是通过不断地traversal来找到你要的东西。
也就是说，你在一个LinkedList里面存了3个data，你要拿index为2的data，就会先从找index 0的下一个，然后再找index 1的下一个。
因为Linked List在insert或者add data进去时只需要记录这个新的data的上一个和下一个data，所以insert的时候会比别的data structure快。

歩む

这里是sample，因为是临时写的，很乱，但是基本的功能都有了，你自己看看吧，那些exception我也懒惰catch了。

1. 
   
2. public class LinkedList
   
3. {
   
4.         private class Node
   
5.         {
   
6.                 public Node nextNode;
   
7.                 public Object data;
   
8.                
   
9.                 public Node(Object data)
   
10.                 {
    
11.                         this.data = data;
    
12.                 }
    
13.         }
    
14.        
    
15.         private Node firstNode;
    
16.        
    
17.         public LinkedList()
    
18.         {
    
19.                 firstNode = new        Node(0);
    
20.         }
    
21.        
    
22.         public boolean add(int index, Object object)
    
23.         {
    
24.                 if (index < ((Integer)firstNode.data))
    
25.                 {
    
26.                         Node current = firstNode;
    
27.                         for (int i = 0; i < index; i++)
    
28.                                 current = current.nextNode;
    
29.                        
    
30.                         Node node = new Node(object);
    
31.                         node.nextNode = current.nextNode;
    
32.                         current.nextNode = node;
    
33.                         firstNode.data = ((Integer)firstNode.data) + 1;
    
34.                        
    
35.                         return true;
    
36.                 }
    
37.                
    
38.                 return false;
    
39.         }
    
40.        
    
41.         public boolean add(Object object)
    
42.         {
    
43.                 Node current = firstNode;
    
44.                 while (current.nextNode != null)
    
45.                         current = current.nextNode;
    
46.                
    
47.                 Node node = new Node(object);
    
48.                 current.nextNode = node;
    
49.                 firstNode.data = ((Integer)firstNode.data) + 1;
    
50.                
    
51.                 return true;
    
52.         }
    
53.        
    
54.         public Object get(int index)
    
55.         {
    
56.                 Node current = firstNode.nextNode;
    
57.                 for (int i = 0; i < index; i++)
    
58.                         current = current.nextNode;
    
59.                
    
60.                 return current.data;
    
61.         }
    
62.        
    
63.         public Object remove(int index)
    
64.         {
    
65.                 Node current = firstNode.nextNode;
    
66.                 for (int i = 0; i < index - 1; i++)
    
67.                         current = current.nextNode;
    
68.                
    
69.                 Node result = current.nextNode;
    
70.                 current.nextNode = null;
    
71.                 return result;
    
72.         }
    
73.        
    
74.         public boolean contains(Object object)
    
75.         {
    
76.                 Node current = firstNode;
    
77.                 while (current.nextNode != null)
    
78.                 {
    
79.                         current = current.nextNode;
    
80.                         if (current.data.equals(object))
    
81.                                 return true;
    
82.                 }
    
83.                
    
84.                 return false;
    
85.         }
    
86.        
    
87.         public boolean isEmpty()
    
88.         {
    
89.                 return firstNode.nextNode == null;
    
90.         }
    
91.        
    
92.         public void clear()
    
93.         {
    
94.                 firstNode = new Node(0);
    
95.         }
    
96. }
    

复制代码

莲花

歩む 发表于 9-4-2013 07:56 PM
这里是sample，因为是临时写的，很乱，但是基本的功能都有了，你自己看看吧，那些exception我也懒惰catch了 ...

真的谢谢你，我现在只学着c programming， 虽然不是很明白，但还是很谢谢你~

它跟last in last out 有什么关系？

歩む

莲花 发表于 9-4-2013 08:10 PM
真的谢谢你，我现在只学着c programming， 虽然不是很明白，但还是很谢谢你~

它跟last in last out 有 ...

last in last out 说的是queue，不是LinkedList，如字面上所说，就像排队一样，最后一个进来的只能最后一个出去。

莲花

歩む 发表于 9-4-2013 10:35 PM
last in last out 说的是queue，不是LinkedList，如字面上所说，就像排队一样，最后一个进来的只能最后一 ...

ohh, queue 还有stack 的 coding 会有什么分别？
linked list 的 source code 是不是struct 里面又有struct*next node ?

歩む

莲花 发表于 10-4-2013 11:09 PM
ohh, queue 还有stack 的 coding 会有什么分别？
linked list 的 source code 是不是struct 里面又有str ...

嗯，有那个nextnode的原因就是linkedlist就是用这种第一个记着下一个node，下一个node记得再下一个node的方式来保存data的。
queue也就和你说的一样last in last out，和排队一样，stack就不同，可以理解为一个罐子，我放了a进去，再放b进去，最后是c，接着我就拿不到a和b了，只能先把c拿出来，就是last in first out。

我也只有一年工作经验，恐怕说的不完全对，你参考一下就行了。

莲花

歩む 发表于 11-4-2013 12:17 AM
嗯，有那个nextnode的原因就是linkedlist就是用这种第一个记着下一个node，下一个node记得再下一个node的 ...

在c programming 的 source code 里，他们有什么分别？
谢谢~~

歩む

c的话，因为是没有oop性质的language，所以大概是这样:

struct Node
{
    void* data;
    struct Node* next;
}

你可以看到，非常简陋，基本上我想拿到第12个node我就需要for loop12次。

歩む

莲花 发表于 11-4-2013 05:18 PM
在c programming 的 source code 里，他们有什么分别？
谢谢~~

还有就是，我觉得你以其学着c，不如直接学c＋＋之类的oop language，你会爱上oop的。

geekman

歩む 发表于 11-4-2013 06:23 PM
还有就是，我觉得你以其学着c，不如直接学c＋＋之类的oop language，你会爱上oop的。

残念，现在很多学院/大学的不长进的教师们还在教着C， 而且还是Console C。。。

geekman

莲花 发表于 9-4-2013 08:10 PM
真的谢谢你，我现在只学着c programming， 虽然不是很明白，但还是很谢谢你~

它跟last in last out 有 ...

Last In Last Out， 缩写LILO，也叫做First In First Out （FIFO），也有人称之为Pipe， 因为存入在里面的数据就好像流入水喉的水，先进入的那一滴水会先从另一边流出来。

First In Last Out/Last In First Out，也称为Stack，因为数据就像一层层的货物一般，先存进去的会被后来的压住，要把东西拿出来就得把后面存进去的先拿出来。

两者之间的差别只是在于你的Data Pointer（指向要优先拿出来的数据的Pointer）如何运作，Pipe的Data Pointer永远指向数据的最前端（D0），每个数据都会有一个指标指向下一个数据（D0指向D1，D1指向D2，D2指向D3，以此类推，直到最后的Dn后面没有东西），当你提取数据的时候，先被提取的将会是D0，这时Data Pointer就会被更新，指向D1，当D1 被提取之后就会被更新去指向D2，etc...

Stack则是相反，Data Pointer永远指向最后进去的数据，自然在提取数据时就会优先提取最后一个。

Stack和Pipe都可以是Link List， 不过 Linked List是自由的连接数据，就像一条链子一般，Data Pointer可以自由移动（如果是Bi-directional Linked List，可以双向，也就是前后移动，Single-directional Linked List则只能单向移动罢了），同时Linked List也可以是Linear List，也就是像Pipe一样，水喉一条，只是在Linked List里面，你可以自由移动Data Pointer，随意的提取任何数据，也可以将数据塞入任何位置。另一种Linked List则是Circular List，头尾相连，没有所谓哪里开头哪里结束。

莲花

geekman 发表于 12-4-2013 08:09 PM
Last In Last Out， 缩写LILO，也叫做First In First Out （FIFO），也有人称之为Pipe， 因为存入在里面的 ...

谢谢你~~

小白_86

嗨，您好！我不知道您到了什么程度，如果是初学者的话，建议学习linked list之前把pointer的concept搞好，对你读code有很大的帮助。以下是我以前写的linked list虽然不是很完整而写的目的是要明白什么是linked list。

1. /* Linked List act as memory effciency array.
   
2. * Not like array, linked list does not need pre-defined size.
   
3. * It is dynamic allocatiion memory block only when caller need to store more data */
   
4. 
   
5. //linked_list.c
   
6. 
   
7. #include <stdlib.h>
   
8. #include <stdio.h>
   
9. #include <string.h>
   
10. #include "linked_list.h"
    
11. 
    
12. LinkedListItem* linked_list_item_create() {
    
13.         LinkedListItem* linked_list_item = NULL;
    
14.        
    
15.         linked_list_item = (LinkedListItem*)malloc(sizeof(*linked_list_item));
    
16.        
    
17.         memset(linked_list_item, 0, sizeof(linked_list_item));
    
18.        
    
19.         return linked_list_item;
    
20. }
    
21. 
    
22. void linked_list_item_destroy(LinkedListItem* linked_list_item) {
    
23.        
    
24.         if(!linked_list_item)
    
25.                 return;
    
26.                
    
27.         free(linked_list_item);       
    
28.        
    
29. }
    
30. 
    
31. void linked_list_append(LinkedList* linked_list, void* data) {
    
32.        
    
33.         LinkedListItem* linked_list_item = NULL;
    
34.        
    
35.         if((!linked_list) || (!data))
    
36.                 return;
    
37.        
    
38.         linked_list_item = linked_list_item_create();
    
39.         linked_list_item->data = data;
    
40.        
    
41.         if(linked_list->len == 0) {
    
42.                 linked_list->head = linked_list_item;
    
43.                 linked_list->tail = linked_list_item;
    
44.         }
    
45.         else {
    
46.                 /* Modify next apppender link */
    
47.                 linked_list_item->previous = linked_list->tail;
    
48.                 linked_list_item->next = NULL;
    
49.                
    
50.                 /* Modify previous apppender link */
    
51.                 linked_list->tail->next = linked_list_item;
    
52.                
    
53.                 /* update tail item */
    
54.                 linked_list->tail = linked_list_item;
    
55.         }
    
56.        
    
57.         linked_list->len++;
    
58. }
    
59. 
    
60. void* linked_list_extract_first(LinkedList* linked_list) {
    
61.        
    
62.         LinkedListItem* previous = NULL;
    
63.         void* data = NULL;
    
64.        
    
65.         if(!linked_list || linked_list->head == NULL)
    
66.                 return NULL;
    
67.        
    
68.         data = linked_list->head->data;
    
69.                
    
70.         if(linked_list->head->next == NULL) {
    
71.                 linked_list_item_destroy(linked_list->head);
    
72.                 linked_list->head = NULL;
    
73.                 linked_list->tail = NULL;
    
74.         }
    
75.         else {
    
76.                 linked_list->head = linked_list->head->next;
    
77.                 linked_list_item_destroy(linked_list->head->previous);
    
78.                 linked_list->head->previous = NULL;
    
79.         }
    
80.        
    
81.         linked_list->len--;
    
82.        
    
83.         return data;
    
84. }
    
85. 
    
86. LinkedList* linked_list_create() {
    
87.         LinkedList* linked_list = NULL;
    
88.        
    
89.         linked_list = (LinkedList*)malloc(sizeof(*linked_list));
    
90.        
    
91.         memset(linked_list, 0, sizeof(linked_list));
    
92.        
    
93.         linked_list->append = linked_list_append;
    
94.         linked_list->extract_first = linked_list_extract_first;
    
95. }
    
96. 
    
97. 
    

复制代码

1. #ifndef _LINKED_LIST_H
   
2. #define _LINKED_LIST_H
   
3. 
   
4. //linked_list.h
   
5. 
   
6. typedef struct LinkedList LinkedList;
   
7. 
   
8. typedef struct LinkedListItem LinkedListItem;
   
9. 
   
10. struct LinkedListItem {
    
11.         LinkedListItem* previous;
    
12.         LinkedListItem* next;
    
13.         void* data;       
    
14. };
    
15. 
    
16. /* Data structure describe linked list properties and its general function */
    
17. struct LinkedList {
    
18.         LinkedListItem* head;
    
19.         LinkedListItem* tail;
    
20.         unsigned int len;       
    
21.        
    
22.         /* General function */
    
23.         void (*append)(LinkedList* linked_list, void* data);
    
24.         void* (*extract_first)(LinkedList* linked_list);
    
25. };
    
26. 
    
27. LinkedList* linked_list_create();
    
28. 
    
29. void* linked_list_extract_first(LinkedList* linked_list);
    
30. 
    
31. void linked_list_append(LinkedList* linked_list, void* data);
    
32. 
    
33. #endif

复制代码

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include "linked_list.h"
   
5. 
   
6. //test.c
   
7. 
   
8. int main() {
   
9.        
   
10.         LinkedList* ll = NULL;
    
11.         char* data = NULL;
    
12.        
    
13.         ll = linked_list_create();
    
14.        
    
15.         if(ll->extract_first(ll) == NULL) {
    
16.                 printf("is NULL\n");
    
17.         }
    
18.        
    
19.         data = "hello";
    
20.        
    
21.         ll->append(ll, data);
    
22.        
    
23.         data = "world";
    
24.        
    
25.         ll->append(ll, data);
    
26.        
    
27.         printf("data = %s\n", (char*)ll->extract_first(ll));
    
28.         printf("data = %s\n", (char*)ll->extract_first(ll));
    
29.        
    
30.         if(ll->extract_first(ll) == NULL) {
    
31.                 printf("is NULL\n");
    
32.         }
    
33.        
    
34.         return 0;
    
35. }

复制代码

简单来说，linked list就像array, 只是array 要预先defined size, 比如 unsigned int id[10]; 那么最多就只可以储存10个id。
linked list 是无限量的，只要电脑还有足够的memory。
还有就是其实C语言并不是大家所说的无法实现OOP。