<commit_before>---
layout: blog
istop: true
title: "Linux双向链表和hash链表单向链表"
background-image: http://ot1cc1u9t.bkt.clouddn.com/17-7-16/38390376.jpg
date:  2017-07-16 23:45:56
category: Linux内核
tags:
- list
- hashlist
- map表
- 双向链表
- 单向链表
- 线性表
- 兰德
- 链表
---

# 什么是链表

链表（Linked list）
 
是一种常见的基础数据结构，是一种`线性表`，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)

## 说到链表必须要说兰德下 

Rand 是什么？美国智囊团 社会简称`兰德学派` 1946年成立，有多牛：
 
从1950年的朝鲜战争，到60年代的越南战争，70年代信息技术，再到八、九十年代的苏联解体、两德合并、后冷战时代战略，乃至最近的中东问题、台湾问题、朝鲜问题等，无一不是全球万众瞩目的“明星”问题。对这些问题开展研究。
链表就是Rand在1955-1956搞得人工智能程序。有点远了...

# 链表是怎么来的
 
链表开发于1955-1956，编写的信息处理语言（IPL）中做为原始数据类型所编写 IPL是用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。 由当时所属于兰德公司（英语：Rand）的艾伦纽维尔（<NAME>ell），克里夫肖（<NAME>）和赫伯特西蒙（<NAME>）。


## 链表示一种线性表但是为什么比线性表更快

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1) ---维基百科（不过还是不能理解啊）

### 链表个人理解：

链表结构决定了链表是一种``以空间换时间``
 
链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

## 链表怎么实现
Lisp和Scheme这样的语言的`内建数据类型`中就包含了链表的访问和操作
程序语言或面向对象语言，如C/C++和Java依靠易变工具来生成链表 这只是一个栗子，其他面向对象语言也可以生成链表
链表不受语言和平台限制（windows Linux unix）等都有。

# 单向链表是什么
<commit_msg>fix blog<commit_after>---
layout: blog
istop: true
title: "Linux双向链表和hash链表单向链表"
background-image: http://ot1cc1u9t.bkt.clouddn.com/17-7-16/38390376.jpg
date:  2017-07-17 20:45:16
category: Linux内核
tags:
- list
- hashlist
- map表
- 双向链表
- 单向链表
- 线性表
- 兰德
- 链表
---

# 什么是链表

链表（Linked list）
 
是一种常见的基础数据结构，是一种`线性表`，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)

## 说到链表必须要说兰德下 

Rand 是什么？美国智囊团 社会简称`兰德学派` 1946年成立，有多牛：
 
从1950年的朝鲜战争，到60年代的越南战争，70年代信息技术，再到八、九十年代的苏联解体、两德合并、后冷战时代战略，乃至最近的中东问题、台湾问题、朝鲜问题等，无一不是全球万众瞩目的“明星”问题。对这些问题开展研究。
链表就是Rand在1955-1956搞得人工智能程序。兰德和DARPA有点类似是非营利性机构，有点远了...

# 链表是怎么来的
 
链表开发于1955-1956，编写的信息处理语言（IPL）中做为原始数据类型所编写 IPL是用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。 由当时所属于兰德公司（英语：Rand）的艾伦纽维尔（<NAME>），克里夫肖（<NAME>）和赫伯特西蒙（<NAME>）。


## 链表示一种线性表但是为什么比线性表更快

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1) ---维基百科（不过还是不能理解啊）

### 链表个人理解：

链表结构决定了链表是一种``以空间换时间``
 
链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

## 链表怎么实现
Lisp和Scheme这样的语言的`内建数据类型`中就包含了链表的访问和操作
程序语言或面向对象语言，如C/C++和Java依靠易变工具来生成链表 这只是一个栗子，其他面向对象语言也可以生成链表
链表不受语言和平台限制（windows Linux unix）等都有。

# 单向链表是什么

{'fraction_non_alphanumeric': 0.12695725772323319, 'fraction_numerical': 0.05078290308929327, 'mean_word_length': 8.307086614173228, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6525926', 'n_tokens_mistral': 2038, 'n_tokens_neox': 2388, 'n_words': 105}