php实现链表反转,php数组用foreach循环后，怎么求和呢？

关于“php实现链表”的问题，小编就整理了【3】个相关介绍“php实现链表”的解答：

foreach在php5里只需要走一遍链表，php7只要顺序遍历一遍bucket数组。while循环要走hash find

每次将待插入的结点链在单链表的最后一个结点的后面 void creatlist(LinkList *L; Datatype a[10]) { L = (LinkList *) malloc (sizeof(struct node)); L->next = NULL;                   //生成头结点    r = L;                            //r为指向表尾的指针 for(i = 0; i<=9; i++) { p = (LinkList *) malloc (sizeof(struct node)); p->data = a[i];          //生成新的结点 p->next = NULL; r->next = p;             //将新生成的结点插在表尾 r = p;                   //将表尾指针指向新插入的结点 } }

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

实现LRU

1. 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

3. 利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

对于第一种方法， 需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

到此，以上就是小编对于“php实现链表”的问题就介绍到这了，希望介绍关于“php实现链表”的【3】点解答对大家有用。