Java语言中链表和双向链表
链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构。Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义，而非语言提供的数据类型)，所以我们可以编写这样的类来实现链表中的结点。
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的示意图：
链表的数据结构
我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位，使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值，并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在当前结点前插入一个结点，并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length＋＋;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length－－;
}
return temp;
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*链表的简单应用举例*/
{
List a=new List ();
for(int i=1;i<=10;i＋＋)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。

C语言实现链表之双向链表（十二）判断链表是否为空和获取链表长度


    上一篇文章给出了设置结点数据与获取结点数据的两个函数，本篇文章将给出判断链表是否为空和获取链表长度的函数，共两个函数。



/*============================================================================== 
*   操作  ：检查链表是否为空
*   操作前：pHeadNode为链表的头指针
*   操作后：如果链表为空，则返回TRUE，否则返回FALSE
==============================================================================*/
C_Bool CheckMyListEmpty(MyListNode* pHeadNode)
{
    if(pHeadNode == NULL)
    {
        printf("The list is empty.\n");
        return TRUE;
    }
    else
    {
        printf("The list is no empty.\n");
        return FALSE;
    }
}

/*============================================================================== 
*   操作  ：获得链表的长度
*   操作前：pHeadNode为链表的头指针
*   操作后：返回链表的长度
==============================================================================*/
int GetMyListLen(MyListNode* pHeadNode)
{
    MyListNode* pListNodeTmp = pHeadNode;
    int iLen = 0;

    // 判断是否有链表输入
    if(pHeadNode == NULL)
    {
        fprintf(stderr, "There is no list.\n");
        return -1;
    }

    // 获得长度
    while(pListNodeTmp != NULL)
    {
        iLen++;
        pListNodeTmp = pListNodeTmp->pNextNodeAddr;
    }
    return iLen;
}

    这两个函数比较简单，对于常见的错误处理以及布尔变量此处不再过多去说，大家一看便知。

Python数据结构与算法：第3-9课时：双向链表及添加元素、判断链表是否为空


双向链表




后继节点，某个节点，前驱节点。


例子：
比如40这个节点的前驱节点就是100，  后继节点就是6




定义：
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

所需要的一些操作：
•	is_empty() 链表是否为空

•	length() 链表长度

•	travel() 遍历链表

•	add(item) 链表头部添加

•	append(item) 链表尾部添加

•	insert(pos, item) 指定位置添加

•	remove(item) 删除节点

•	search(item) 查找节点是否存在

实现
节点的代码：
class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

self.next 为后继节点的地址，

prev  为前继节点的地址。


双链列表定义的代码：
只需要顶一个函数头就可以了，和单链列表一样。
class DLinkList(object):
    """双向链表"""
    def __init__(self,node = None):
        self._head = node



判断链表是否为空：
def is_empty(self):
    """判断链表是否为空"""
    return self._head == None

与单向链表一样。


判断双向链表的长度：
与单向链表一样：
只需要从头遍历到尾就可以实现了。
def length(self):
    """返回链表的长度"""
    cur = self._head
    count = 0
    while cur != None:
        count += 1
        cur = cur.next
    return count



遍历双向链表的长度：
也与单链列表一致：
def travel(self):
    """遍历链表"""
    cur = self._head
    while cur != None:
        print(cur.item)
        cur = cur.next



在头部插入一个节点 add：


让 之前表头self._head指向 新节点node地址。
实现代码：
def add(self, item):
    """头部插入元素"""
    node = Node(item)
    if self.is_empty():
        # 如果是空链表，将_head指向node
        self._head = node
    else:
        # 将node的next指向_head的头节点
        node.next = self._head
        # 将_head的头节点的prev指向node
        self._head.prev = node
        # 将_head 指向node
        self._head = node



在双向链表尾部添加元素：
实现代码：
def append(self, item):
    """尾部插入元素"""
    node = Node(item)
    if self.is_empty():
        # 如果是空链表，将_head指向node
        self._head = node
    else:
        # 移动到链表尾部
        cur = self._head
        while cur.next != None:
            cur = cur.next
        # 将尾节点cur的next指向node
        cur.next = node
        # 将node的prev指向cur
        node.prev = cur



在双向链表尾指定位置插入元素：
有数双向链表将节点的头尾均连起来，所以只需要一个游标就可以实现了。
实现代码：
def insert(self, pos, item):
    """在指定位置添加节点"""
    if pos <= 0:
        self.add(item)
    elif pos > (self.length()-1):
        self.append(item)
    else:
        node = Node(item)
        cur = self._head
        count = 0
        # 移动到指定位置的前一个位置
        while count < (pos-1):
            count += 1
            cur = cur.next
        # 将node的prev指向cur
        node.next = cur
        # 将node的next指向cur的下一个节点
        node.prev = cur.prev
        # 将cur的下一个节点的prev指向node
        cur.prev.next = node
        # 将cur的next指向node
        cur.prev = node

一、循环链表


循环链表是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）


优点：从表中任一结点出发均可找到表中其他结点


注意：由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断他们是否等于头指针


循环条件
p!=NULL                  →                p!=L
p->next!=NULL       →                p->next!=L
​     单链表                                      单循环链表


带尾指针循环链表的合并


LinkList Connect(LinkList Ta,LinkList Tb)
{
    p=Ta->next;
    Ta->next=Tb->next->next;
    delete Tb->next;
    Tb->next=p;
    return Tb;
}

二、双向链表


双向链表：在单链表的每个结点里再增加一个指向其前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表


双向循环链表：和单链的循环表类似，双向链表也可以有循环表

让头结点的前驱指针指向链表的最后一个结点
让最后一个结点的后继指针指向头结点



双向链表结构的对称性：
p->prior->next = p = p->next->prior


三、双向链表的插入
void ListInsert_DuL(DuLinkList &L,int i,ElemTyoe e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    s=new DuLNode;
    s->date=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
}

四、双向链表的删除
void ListDelete_DuL(DuLink &L,int i,ElemType &e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}