数组：
数组中元素储存在连续的内存位置，声明数组时可以指定数组的大小，限制数组可以存储的元素数量。
但如果事先不知道元素的大小，可以申请一个足够大的数组，但是内存中可能没有足够大连续内存空间，如何合理地利用内存中的非连续空间呢
链表：一种非常灵活的动态数据结构，不将其元素存储在连续的内存位置中，所以可以任意添加链表元素的数量
链表与数组的不同：链表中的数据在内存中并不是顺序存储的，而是通过在链表的每个元素中，保存指向下一个元素的引用，来找到下一个元素。
struct LNode{
int data;
struct LNode * next;
};
struct LNode *head, *middle,*last;
head=(LNode *)malloc(sizeof(struct LNode));
middle=(LNode *)malloc(sizeof(struct LNode));
last=(LNode *)malloc(sizeof(struct LNode));
//数据域赋值
head->data=10;
middle->data=20;
last->data=30;
//指针域
head->next=middle;
middle->next=last;
last->next=NULL;
struct LNode *temp=head;
while(temp!=NULL){
print("%d ",temp->data);
temp=temp->next;
}
data数据域：可以存放该节点对应的任何数据类型，如int、char、float；next指针域：指向链表中下一个节点的引用指针
单向链表
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
- 表元素域elem用来存放具体的数据
- 链接域next用来存放下一个节点的位置（python中的标识）
- 变量p指向链表的头节点head的位置，从p出发能找到链表中的任意节点
节点实现
class SingleNode(object):
"""单链表的节点"""
def __init__(self,item):
# _item存放数据元素
self.item=item
# _next是下一个节点的标识
self.next=None
用一个类来表示一个节点
class Node{
constructor(value,next=null){
this.value=value;
this.next=next;
}
}
单链表的实现
定义链表class
class LinkedList{
constructor(value){
this.head=new Node(value);
}
}
单链表的操作
- is_empty() 链表是否为空
- length() 链表长度
- travel() 遍历整个链表
- add(item) 链表头部添加元素
- append(item) 链表尾部添加元素
- insert(pos,item) 指定位置添加元素
- remove(item) 删除节点
- search(item) 查找节点是否存在
给定一个值，查找对应的节点
findNode(value){
let currentNode=this.head;
while(currentNode.value!=value){
currentNode=currentNode.next;
}
if(!currentNode){
return null;
}
return currentNode;
}
在指定节点后面插入新节点
insertAfter(value,newValue){
const newNode=new Node(newValue);
const currentNode=this.findNode(value);
newNode.next=currentNode.next;
currentNode.next=newNode;
}
在尾部添加节点
append(value){
const newNode=new Node(value);
let currentNode=this.head;
while(currentNode.next){
currentNode=currentNode.next;
}
currentNode.next=newNode;
}
在头部插入节点
prepend(value){
const newNode=new Node(value);
newNode.next=this.head;
this.head=newNode;
}
删除指定节点
remove(value){
let currentNode=this.head;
let previousNode=null;
while(currentNode.value!=value){
previousNode=currentNode;
currentNode=currentNode.next;
}
if(currentNode==this.head){
this.head=currentNode.next;
}else{
previousNode.next=currentNode.next;
}
}
删除头部节点
removeHead(){
this.head=this.head.next;
}
删除尾部节点
removeTail(){
let currentNode=this.head;
let previousNode=null;
while(currentNode.next){
previousNode=currentNode;
currentNode=currentNode.next;
}
previousNode.next=null;
}
遍历链表
traverse(){
let currentNode=this.head;
while(currentNode){
console.log(currentNode.value);
currentNode=currentNode.next;
}
}
双链表
class Node{
constructor(value,next=null,pre=null){
this.value=value;
this.next=next;
this.pre=pre;
}
}
循环链表
class LinkedList{
constructor(value){
this.head=new Node(value);
//初始tail就是head
//添加节点后，tail.next=head
this.tail=this.head;
}
}
