数组：
数组中元素储存在连续的内存位置，声明数组时可以指定数组的大小，限制数组可以存储的元素数量。
但如果事先不知道元素的大小，可以申请一个足够大的数组，但是内存中可能没有足够大连续内存空间，如何合理地利用内存中的非连续空间呢
链表：一种非常灵活的动态数据结构，不将其元素存储在连续的内存位置中，所以可以任意添加链表元素的数量
链表与数组的不同：链表中的数据在内存中并不是顺序存储的，而是通过在链表的每个元素中，保存指向下一个元素的引用，来找到下一个元素。

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=headthis.tail=this.head;}}