已知有一个单向循环链表，其每个结点中含三个域：prior，data 和 next，其中 data 域为数据域，next 为指向后继结点的指针域，prior 也为指针域,但它的值为空 (NULL) ，试编写算法将此单向循环链表改为双向循环链表，即使 prior 成为指向前驱结点的指针域。
输入共有三行，第一行为该单向循环链表的长度 n（1≤n≤50）；第二行为该单向循环链表的各个元素 aii（1≤ai ≤1000），它们各不相同且都为数字；第三行为一个数字 m，表示链表中的一个元素值，要求输出时以该元素为起点反向输出整个双向链表。
输出为一行，即完成双向链表后以反向顺序输出该链表，每两个整数之间一个空格，最后一个整数后面没有空格。
1 #include &iostream&
2 using namespace
4 class Node {
Node * pre, *
Node(const int &_data) {
15 class LinkedList {
16 private:
18 public:
LinkedList() {
~LinkedList() {
if (head == nullptr) {
Node * current_node = head -&
head -& next =
current_node -& pre =
while (current_node != nullptr) {
Node * delete_node = current_
current_node = current_node -&
delete delete_
void insert(Node *node, int index) {
if (head == nullptr) {
if (index != <span style="color: #) {
head -& next =
if (index == <span style="color: #) {
node -& next = head -&
head -& next =
Node * current_node = head -&
int count = <span style="color: #;
while (current_node
!= head && count & index - <span style="color: #) {
current_node = current_node-&
if (count == index - <span style="color: #) {
node-&next = current_node-&
current_node-&next =
if (node == head -& next) {
void dualOutput(const int &value) {
if (head == nullptr) {
Node * current_node =
while (current_node -& data != value) {
current_node = current_node -&
if (current_node -& data == value) {
Node * end_node = current_node -&
while (current_node -& pre != end_node) {
cout && current_node -& data && " ";
current_node = current_node -&
cout && current_node -& data && " ";
cout && end_node -& data &&
void dualDirection() {
if (head == nullptr) {
Node * current_node = head -&
while (current_node != head) {
current_node -& next -& pre = current_
current_node = current_node -&
head -& next -& pre =
void output() {
if (head == nullptr) {
Node * current_node = head -&
cout && current_node -&
while (current_node -& next != head -& next) {
current_node = current_node -&
<span style="color: #0
cout && " " && current_node -&
<span style="color: #1
<span style="color: #2
<span style="color: #3
<span style="color: #4
void reverseOutput() {
<span style="color: #5
if (head == nullptr) {
<span style="color: #6
<span style="color: #7
<span style="color: #8
Node * current_node =
<span style="color: #9
cout && current_node -&
<span style="color: #0
while (current_node -& pre != head) {
<span style="color: #1
current_node = current_node -&
<span style="color: #2
cout && " " && current_node -&
<span style="color: #3
<span style="color: #4
<span style="color: #5
<span style="color: #6 };
<span style="color: #7
<span style="color: #8 int main() {
<span style="color: #9
<span style="color: #0
<span style="color: #1
<span style="color: #2
for (int i = <span style="color: #; i & ++i) {
<span style="color: #3
<span style="color: #4
<span style="color: #5
auto * node = new Node(num);
<span style="color: #6
linkedlist.insert(node, i);
<span style="color: #7
//linkedlist.output();
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
<span style="color: #2
linkedlist.dualDirection();
<span style="color: #3
//linkedlist.reverseOutput();
<span style="color: #4
linkedlist.dualOutput(key);
<span style="color: #5
<span style="color: #6
return <span style="color: #;
<span style="color: #7 }
阅读(...) 评论()Java-----Collection 实现的LinkedList(双向链表)
Java—–Collection 实现的LinkedList(双向链表)
Linkedlist，双向链表，优点，增加删除，用时间很短，但是因为没有索引，对索引的操作，比较麻烦，只能循环遍历，但是每次循环的时候，都会先判断一下，这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半 ，而不是全部遍历。
双向链表，都有一个previous和next， 链表最开始的部分都有一个fiest和last 指向第一个元素，和最后一个元素。增加和删除的时候，只需要更改一个previous和next，就可以实现增加和删除，所以说，LinkedList对于数据的删除和增加相当的方便。
熟悉链表算法就知道是什么原因，接下来详细讲解一下链表算法，首先给大家看一下我简单实现的链表node：
class LinkNode&T& {
public LinkNode(LinkNode&T& next, LinkNode&T& previous, T obj) {
this.next =
this.previous =
this.obj =
private LinkNode&T&
private LinkNode&T&
* 删除节点
public void remove() {
next.previous =
previous.next =
* 修改节点
public void set(T t) {
LinkNode&T& link = new LinkNode&T&(next, previous, t);
next.previous =
previous.next =
public String toString() {
return obj.toString();
从这段代码可以看出：
　　1、当前对象保存着上一个和下一个对象的引用
private LinkNode&T&
private LinkNode&T&
　2、remove一个对象（这里有点不好理解，你可以把链表想成一个锁链，形象思维。）：
2.1、当前对象的previous对象的next对先指向的当前对象next。
　2.2、当前对象的next对象previous指向当前对先previous。
next.previous =//前与后相连
previous.next = next;//后与前相连
这样就实际上把要删除的对象挤出链接里了。
　　3、set一个对象(理解删除这里就比较好理解)：
　　　　1、创建一个新对象，这个对象的next和previous与当前对象相同。
　　　　2、把this.next.previous指向新创建的对象。
　　　　3、把this.previous.next指向新创建的对象。
public void set(T t) {
LinkNode&T& link = new LinkNode&T&(next, previous, t);
next.previous = link;
previous.next = link;
这样这个对象就被替换掉了。
java 操作双向链表
双向链表的Java实现，以及相关函数的实现
Java 中的 LinkedList 是单向链表还是双向链表？
JAVA实现双向链表终极解析！！熟练使用接口
双向链表(LinkedList)
Java LinkedList双向链表源码分析
Java中LinkedList原理解析
java数据结构与算法之双链表设计与实现
JAVA实现双向链表
java 单向和双向链表的详解
没有更多推荐了，php中的单项链表与双向链表
（一）什么是链表？
链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。
所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。
1、那么先从单向链表着手，先看看单向链表的模拟图：
单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。
2、双向链表：
从上图可以很清晰的看出，每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。
3、循环链表：
循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。
参考：http://zh.wikipedia.org/wiki/链表
（二）链表有什么作用？
链表本质上就是一种，主要用来动态放置数据。也可用来构建许多数据结构，比如堆栈、队列及它们的派生。
（三）链表的实现？
1、单向链表的实现
（1）单向链表的创建过程：
第一步：定义节点的数据结构；
第二步：创建一个空表。
第三步：利用malloc（）向系统申请分配一个节点。
第四步：将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点连接到表尾。
第五步：判断是否有后续节点，如有则转入第三步，否则结束。
（2）单向链表的输出过程：
第一步：找到表头。
第二步：若为非空表，则输出节点的值成员，是空表则退出。
第三步：跟踪链表，找到下一节点的地址。
第四步：转到第二步。
//单项链表实现
单链表，节点只有一个指针域的链表。节点包括数据域和指针域。
　　因此用面向对象的思维，节点类的属性就有两个：一个data（表示存储的数据），一个指针next（链表中指向下一个节点）。
　　链表一个很重要的特性，就是这个头节点$head。它绝对不能少，每次遍历都要从它开始，并且不能移动头节点，应该用一个变量去代替他移动。脑袋里要有链表的结构。这是关键。
　　来一段代码：
3 class Node{
public $data = '';
public $next = null;
function __construct($data)
$this-&data = $data;
13 // 链表有几个元素
14 function countNode($head){
$cur = $head;
while(!is_null($cur-&next)){
$cur = $cur-&next;
return $i;
24 // 增加节点
25 function addNode($head, $data){
$cur = $head;
while(!is_null($cur-&next)){
$cur = $cur-&next;
$new = new Node($data);
$cur-&next = $new;
35 // 紧接着插在$no后
36 function insertNode($head, $data, $no){
if ($no & countNode($head)){
return false;
$cur = $head;
$new = new Node($data);
for($i=0; $i&$no;$i++){
$cur = $cur-&next;
$new-&next = $cur-&next;
$cur-&next = $new;
50 // 删除第$no个节点
51 function delNode($head, $no){
if ($no & countNode($head)){
return false;
$cur = $head;
for($i=0; $i&$no-1; $i++){
$cur = $cur-&next;
$cur-&next = $cur-&next-&next;
63 // 遍历链表
64 function showNode($head){
$cur = $head;
while(!is_null($cur-&next)){
$cur = $cur-&next;
echo $cur-&data, '&br/&';
72 $head = new Node(null);// 定义头节点
75 addNode($head, 'a');
76 addNode($head, 'b');
77 addNode($head, 'c');
79 insertNode($head, 'd', 0);
81 showNode($head);
83 echo '&hr/&';
85 delNode($head, 2);
87 showNode($head);
//双向链表
SPL标准库里实现了几种简单的线性表和树型结构，其中包括了双链表和双链表实现的队列和栈、最大堆、最小堆和优先队列。双链表是一种重要的线性存储结构，对于双链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。
双链表对开发程序来讲是很重要的一种，可以把PHP数组中想想成一个双链表，而PHP内置的SplDoublyLinkedList类通过实现迭代器、数组访问和获取数量的接口使程序访问对象变得访问数组一样方便。
SplDoublyLinkedList类代码如下：
class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable
protected $_llist
= array();
protected $_it_mode = 0;
protected $_it_pos
const IT_MODE_LIFO
const IT_MODE_FIFO
const IT_MODE_KEEP
const IT_MODE_DELETE
public function pop()
if (count($this-&_llist) == 0) {
throw new RuntimeException("Can't pop from an empty datastructure");
return array_pop($this-&_llist);
public function shift()
if (count($this-&_llist) == 0) {
throw new RuntimeException("Can't shift from an empty datastructure");
return array_shift($this-&_llist);
public function push($data)
array_push($this-&_llist, $data);
public function unshift($data)
array_unshift($this-&_llist, $data);
public function top()
return end($this-&_llist);
public function bottom()
return reset($this-&_llist);
public function count()
return count($this-&_llist);
public function isEmpty()
return ($this-&count() == 0);
public function setIteratorMode($mode)
$this-&_it_mode = $mode;
public function getIteratorMode()
return $this-&_it_
public function rewind()
if ($this-&_it_mode & self::IT_MODE_LIFO) {
$this-&_it_pos = count($this-&_llist)-1;
$this-&_it_pos = 0;
public function valid()
return array_key_exists($this-&_it_pos, $this-&_llist);
public function key()
return $this-&_it_
public function current()
return $this-&_llist[$this-&_it_pos];
public function next()
if ($this-&_it_mode & self::IT_MODE_LIFO) {
if ($this-&_it_mode & self::IT_MODE_DELETE) {
$this-&pop();
$this-&_it_pos--;
if ($this-&_it_mode & self::IT_MODE_DELETE) {
$this-&shift();
$this-&_it_pos++;
public function offsetExists($offset)
if (!is_numeric($offset)) {
throw new OutOfRangeException("Offset invalid or out of range");
return array_key_exists($offset, $this-&_llist);
public function offsetGet($offset)
if ($this-&_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this-&_llist)-$offset;
$realOffset = $offset;
if (!is_numeric($offset) || !array_key_exists($realOffset, $this-&_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
return $this-&_llist[$realOffset];
public function offsetSet($offset, $value)
if ($offset === null) {
return $this-&push($value);
if ($this-&_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this-&_llist)-$offset;
$realOffset = $offset;
if (!is_numeric($offset) || !array_key_exists($realOffset, $this-&_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
$this-&_llist[$realOffset] = $value;
public function offsetUnset($offset)
if ($this-&_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this-&_llist)-$offset;
$realOffset = $offset;
if (!is_numeric($offset) || !array_key_exists($realOffset, $this-&_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
array_splice($this-&_llist, $realOffset, 1);
例子说明：
$doubly=new SplDoublyLinkedList();
$doubly-&push('a');
$doubly-&push('b');
$doubly-&push('c');
$doubly-&push('d');
echo '初始链表结构：';
var_dump($doubly);
echo '&br/& 先进先出Keep模式迭代输出： &br/&';
$doubly-&setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
$doubly-&rewind();
foreach($doubly as $key=&$value)
echo $key.' '.$value."&br/&";
echo '&br/&后进先出Keep模式迭代输出：&br/&';
$doubly-&setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP);
$doubly-&rewind();
foreach($doubly as $key=&$value)
echo $key.' '.$value."&br/&";
echo '&br/&后进先出Delete模式迭代输出：&br/&';
$doubly-&setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);
$doubly-&rewind();
foreach($doubly as $key=&$value)
if($key == 1) break;
echo $key.' '.$value."&br/&";
echo '&br/&Delete模式迭代之后的链表：';
var_dump($doubly);
初始链表结构：
object(SplDoublyLinkedList)[1]
private 'flags' =&
private 'dllist' =&
array (size=4)
'a' (length=1)
'b' (length=1)
'c' (length=1)
'd' (length=1)
先进先出Keep模式迭代输出： 0 a1 b2 c3 d后进先出Keep模式迭代输出：3 d2 c1 b0 a后进先出Delete模式迭代输出：3 d2 cDelete模式迭代之后的链表：object(SplDoublyLinkedList)[1]
private 'flags' =&
private 'dllist' =&
array (size=2)
'a' (length=1)
'b' (length=1)
用php实现一个单链表
PHP实现双向链表
PHP实现简单双向链表
PHP之双向链表(SplDoublyLinkedList)简介
韩顺平_PHP程序员玩转算法公开课(第一季)12_双向链表crud操作之_水浒英雄排行_学习笔记_源代码图解_PPT文档整理
PHP实现双向链表并排序 -- 会员排名演示
数组和单向链表的区别
用PHP实现的单链表
PHP数据结构之——链表
剑指offer-反转链表-php
没有更多推荐了，①学习 ②记录 ③表达 ④分享
Java LinkedList双向链表源码分析
LinkedList就传说中的双向链表了。是List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
查看LinkedList的构造函数：
* Constructs an empty list.
public LinkedList() {
header.next = header.previous =
这里的header变量的定义如下：
private transient Entry&E& header = new Entry&E&(null, null, null);
表示双向循环链表的头结点。其中的Entry定义了双向链表的结构：
private static class Entry&E& {
Entry(E element, Entry&E& next, Entry&E& previous) {
this.element =
this.next =
this.previous =
Entry中包括数据元素、前续结点和后续结点。
构造函数即是初始化一个只包含header头结点一个元素的双向链表。
可以得出：LinkedList实质上就是一个双向链表，并把header作为头结点。
查看LinkedList的add(E)方法：
public boolean add(E e) {
addBefore(e, header);
add(E)方法主要指向了addBefore(E, Entry)函数：
private Entry&E& addBefore(E e, Entry&E& entry) {
Entry&E& newEntry = new Entry&E&(e, entry, entry.previous);
newEntry.previous.next = newE
newEntry.next.previous = newE
modCount++;
return newE
这个方法中传入的第二个参数entry为header头结点，表示把元素插入到header头结点之前。然后后两句分别表示设置前续结点的后续结点和后续结点的前续结点。以便连接成双向链表。
可以得出：LinkedList的add(E)方法把新结点插入到header头结点之前，即列表的结尾。
查看LinkedList的set(int, E)方法：
* Replaces the element at the specified position in this list with the
* specified element.
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
public E set(int index, E element) {
Entry&E& e = entry(index);
E oldVal = e.
e.element =
return oldV
这个函数主要是设置某个索引位置的结点。首先调用了entry(int)方法：
* Returns the indexed entry.
private Entry&E& entry(int index) {
if (index & 0 || index &= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry&E& e =
if (index & (size && 1)) {
for (int i = 0; i &= i++)
for (int i = i & i--)
这里首先判断需要设置的位置是否越界，如果越界则抛出异常。然后通过循环找到需要替换的结点。
接下来回到set(int ,E)函数，把旧的结点替换成新的结点，并返回旧的结点。
可以得出：set(int ,E)方法需要循环遍历链表，时间开销比较大。
查看LinkedList的push(E)方法：
* Pushes an element onto the stack represented by this list.
* words, inserts the element at the front of this list.
* &p&This method is equivalent to {@link #addFirst}.
* @param e the element to push
* @since 1.6
public void push(E e) {
addFirst(e);
push(E)方法主要调用了addFirst(E)方法：
* Inserts the specified element at the beginning of this list.
* @param e the element to add
public void addFirst(E e) {
addBefore(e, header.next);
这里继续调用addBefore(E, Entity)表示把新节点插入到header头结点之后。
可以得出：push(E)方法主要是把新节点插入到header头结点之后。
查看LinkedList的pop()方法：
* Pops an element from the stack represented by this list.
* words, removes and returns the first element of this list.
* &p&This method is equivalent to {@link #removeFirst()}.
* @return the element at the front of this list (which is the top
of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
public E pop() {
return removeFirst();
这里继续调用了removeFirst()方法：
* Removes and returns the first element from this list.
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
public E removeFirst() {
return remove(header.next);
这里继续调用remove(Entry&E&)方法：
* Retrieves and removes the head (first element) of this list.
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
private E remove(Entry&E& e) {
if (e == header)
throw new NoSuchElementException();
E result = e.
e.previous.next = e.
e.next.previous = e.
e.next = e.previous =
e.element =
modCount++;
在调用remove(Entry&E&)方法时，传入了header的下一个结点。如果传入的下一个结点是header的话，表示此事链表中只有一个结点header，此时抛出异常。如果找到则删除该节点（注意这里双向链表删除结点时的步骤），并返回被删除的结点。
可以得出：pop()方法删除的是header头结点之后的结点，并返回被删除的结点。
★ LinkedList实质上就是一个双向链表，并把header作为头结点。
★ LinkedList的add(E)方法把新结点插入到header头结点之前。
★ set(int ,E)方法需要循环遍历链表，时间开销比较大。
★ push(E)方法主要是把新节点插入到header结点之前
★ pop()方法删除的是header头结点之后的结点，并返回被删除的结点。
JAVA实现双向链表
Java 中的 LinkedList 是单向链表还是双向链表？
LinkedList 链表
手写LinKedList双向链表
终于搞清了什么是链表结构
自己实现Java中基于双向链表的LinkedList
(8) Java源码分析 ---- LinkedList (对应数据结构中线性表中的双向循环链表，JDK1.6)
双向链表(LinkedList)
LinkedList,双向链表的实现
LinkedList
LinkedList : 双向链表与实现
没有更多推荐了，List-DuLinkedList-将单向循环链表改为双向的_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
List-DuLinkedList-将单向循环链表改为双向的
硕士研究生|
总评分4.4|
用知识赚钱
阅读已结束，下载本文需要
定制HR最喜欢的简历
你可能喜欢