单向链表
单向循环链表
注意：
构造函数名不带泛型
链表 LinkedList
单向链表 SinglyLinkedList
get、set、add、remove、length、isEmpty、clear
get时可直接返回值，set时返回老值(跟Map的put一样)
add时，记得也前节点关联
add时，若为空链表，则将要添加的节点设为头节点
只add元素时，相当于：
add(E element) = add(Integer.MAX_VALUE, element);
单链表结点类Node声明如下：
public class Node<E>
{
public E Data;
public Node<E> Next;
public Node(E data,Node<E> next)
{
this.Data = data;
this.Next = next;
}
public Node(E Data)
{
this(Data,null);
}
public Node()
{
this(null,null);
}
}
Node<E>类有两个成员变量，data表示结点的数据域，保存数据元素本身，数据类型是E；next表示结点的地址域，保存后继结点的地址。
Node类中成员变量next的数据类型是Node类自己，Node类是“自引用的类”。所谓自引用的类(self-referential calss)，是指一个类声明包含一个引用当前类的对象的成员变量。
建立并链接结点的语句如下：
public class MainForm
{
public static void main(String args[])
{
Node<String> CC =new Node<String>("C");
Node<String> BB =new Node<String>("B",CC);
Node<String> AA =new Node<String>("A",BB);
System.out.println(AA.Data);
System.out.println(AA.Next.Data);
System.out.println(AA.Next.Next.Data);
}
}
单链表的头指针head也是一个结点引用，声明如下：
Node<E> head = null;
当head ==null时，表示空单链表。
实现：
public class SinglyLinkedList<E> //单链表类
{
protected Node<E> head; //头指针，指向单链表第一个结点
public SinglyLinkedList() //构造空单链表
{
this.head = null;
}
public SinglyLinkedList(Node<E> head) //构造指定头指针的单链表
{
this.head = head;
}
//判断单链表是否为空
public boolean isEmpty()
{
return this.head == null;
}
//返回单链表长度，单链表遍历算法
public int length()
{
int i = 0;
Node<E> p = this.head;
while(p != null)
{
i ++;
p = p.Next;
}
return i;
}
//返回序号为index的对象，若单链表为空或序号错误则返回null
public E get(int index)
{
if(this.head != null && index >= 0)
{
int j = 0;
Node<E> p = this.head;
while(p != null && j < index)
{
j ++;
p = p.Next;
}
if(p !=null)
{
return (E)p.Data;
}
}
return null;
}
//设置序号为index的对象为element，若操作成功，返回原对象，否则返回null
public E set(int index,E element)
{
if(this.head != null && index >= 0 && element != null)
{
int j = 0;
Node<E> p = this.head;
while(p != null && j < index)
{
j ++;
p = p.Next;
}
if(p != null)
{
E old = (E)p.Data;
p.Data = element;
//若操作成功，则返回原对象
return old;
}
}
//操作不成功
return null;
}
//插入element对象，插入后对象序号为index，若操作成功返回true
public boolean add(int index,E element)
{
if(element ==null)
{
return false; //不能添加空对象(null)
}
//头插入
if(this.head == null || index <= 0)
{
Node<E> q = new Node<E>(element);
q.Next = this.head;
this.head = q;
//this.head = new Node(element,this.head); //头插入，相当于上述3句
}
//单链表不空且index>=1
else
{
int j = 0;
Node<E> p = this.head;
while(p.Next != null && j < index - 1) //寻找插入位置
{
j ++;
p = p.Next;
}
Node<E> q = new Node<E>(element); //中间/尾插入
q.Next = p.Next; //q插入在p结点之后
p.Next = q;
//p.Next = new Node(element,p.Next); //中间/尾插入，相当于上述3句
}
return true;
}
//在单链表最后插入对象
public boolean add(E element)
{
return add(Integer.MAX_VALUE,element);
}
//移去序号为index的对象，若操作成功则返回被移去的对象，否则返回null
public E remove(int index)
{
E old = null;
if(this.head != null && index >= 0)
{
if(index == 0) //头删除
{
old = (E)this.head.Data;
this.head = this.head.Next;
}
else //中间/尾删除
{
int j = 0;
Node<E> p = this.head;
while(p.Next != null && j < index - 1) //定位到待删除结点的前驱结点
{
j ++;
p = p.Next;
}
if(p.Next != null)
{
old = (E)p.Next.Data; //若操作成功，返回被移去对象
p.Next = (p.Next).Next; //删除p的后继结点
}
}
}
return old;
}
//清空单链表
public void clear()
{
this.head = null;
}
//返回所有元素值对应的字符串
public String toString()
{
String str = "(";
Node<E> p = this.head;
while(p != null)
{
str += p.Data.toString();
p = p.Next;
if(p != null)
{
str += ",";
}
}
return str + ")";
}
}
=====================================================================================
链表反转：
public class Node<E> {
public E Data;
public Node<E> Next;
public Node(E data,Node<E> next)
{
this.Data = data;
this.Next = next;
}
public Node(E Data)
{
this(Data,null);
}
public Node()
{
this(null,null);
}
/**
* 递归逆序
*/
@SuppressWarnings({ "null", "unchecked" })
public static Node reverse(Node current){
if(current == null || current.Next == null){
return current;
}
/*
* 方法1：
* 递归，在反转当前节点之前先反转后续节点
Node nextNode = current.Next;
Node newNode = reverse(nextNode);
current.Next = null;
nextNode.Next = current;*/
//法2：
Node newNode = reverse(current.Next);
current.Next.Next = current;
current.Next = null;
return newNode;
}
/**
* 遍历逆序
*
* pre -> cur -> tmp
*
* 将当前节点的下一个节点缓存后更改当前节点指针
* @param current
* @return
*/
public static Node reverse2(Node current) {
if (current == null)
return current;
Node pre = current;// 上一结点
Node cur = current.Next;// 当前结点
Node tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）
while (cur != null) {// 当前结点为null，说明位于尾结点
tmp = cur.Next;
cur.Next = pre;// 反转指针域的指向
// 指针往下移动
pre = cur;
cur = tmp;
}
// 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
current.Next = null;
return pre;
}
public static void main(String[] args) throws Exception {
Node<String> CC = new Node<String>("C");
Node<String> BB = new Node<String>("B", CC);
Node<String> AA = new Node<String>("A", BB);
Node h = AA;
while (null != h) {
System.out.print(h.Data + " ");
h = h.Next;
}
System.out.println("\n**************************");
Node<String> dd = reverse2(AA);
// 打印反转后的结果
while (null != dd) {
System.out.print(dd.Data + " ");
dd = dd.Next;
}
}
}
结果：
A B C
**************************
C B A
相关推荐
单向链表是一种基本的数据结构，它在计算机科学和编程中有着广泛的应用。与数组不同，链表中的元素不是在内存中连续存储的，而是通过指针或引用连接在一起，形成一个逻辑上的线性序列。单向链表的每个节点包含两部分...
本文将详细讲解如何在C#中实现单向链表，结合源码解析来帮助你深入理解其内部机制。 首先，我们要知道什么是单向链表。单向链表是由一系列节点组成，每个节点包含两个部分：数据域和指针域。数据域存储实际的数据，...
单向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在C++编程中，为了实现通用性，我们通常会使用模板类来创建单向链表，以便它可以处理不同类型的元素。标题"单向链表类...
单向链表是一种基本的数据结构，它在计算机科学中被广泛应用，特别是在算法和数据结构的实现中。在Java编程中，单向链表通常通过定义一个节点类来实现，每个节点包含数据和指向下一个节点的引用。下面我们将深入探讨...
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2．遍历单向链表。 3．把单向链表中元素逆置（不允许申请新的结点空间）。 4．在单向链表中删除所有的偶数元素结点。 5．编写在非递减...
在本篇数据结构实验报告中，我们关注的核心是单向链表这一数据结构。单向链表是一种线性数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。实验使用VC++ 6.0作为编程工具，旨在通过实践来深入理解和...
04.单向链表以及单向链表的应用.ppt
这是一个单向链表，它具有插入与删除节点的功能。Entry类实现了链表的各节点。
本文将深入探讨两种重要的线性数据结构——单向链表和双向链表，以及它们在实际编程中的应用。 单向链表是一种线性数据结构，它的每个元素（称为节点）包含两部分：数据域，用于存储实际的数据；指针域，用于存储下...
将一个单向链表反向连接
本资源提供的是针对初学者设计的链表学习材料，包括单向链表和双向链表的实现。下面将详细讲解这两种链表的数据结构及其操作。 1. **单向链表**： 单向链表是一种线性数据结构，每个节点包含两部分：数据域和指针...
单向链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表逆转是计算机科学中常见的操作，它将链表中的元素顺序颠倒，使得原链表的最后一个元素成为新链表的第一个元素，而...
单向链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在本文中，我们将深入探讨如何实现单向链表的各种操作，包括建立链表、添加元素、删除元素、翻转链表（包括递归方法）...
在IT领域，数据结构是编程基础中的重要组成部分，而单向链表作为基本的数据结构之一，在许多场景下都有着广泛的应用。本项目以Flash AS3.0为编程语言，实现了一个单向链表的数据结构，这对于理解和应用单向链表概念...
本主题将深入探讨由C语言实现的单向链表（slist.h）和双向链表（blist）。这两种链表各有特点，适用于不同的场景，对于理解和掌握数据结构与算法至关重要。 ### 单向链表（slist.h） 单向链表是一种线性数据结构，...
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...
单向链表作为一种基础的数据结构，其插入、删除、创建和遍历操作是每个程序员必须熟练掌握的技能。本文将详细介绍如何使用C语言实现单向链表结点的逐个删除。 首先，我们要了解单向链表的基本概念。单向链表是由一...
数据结构，c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
单向链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。在计算机科学中，链表常用于构建动态数据结构，因为它们允许高效的插入和删除操作，尤其是在元素的位置未知时。而基...
单向链表是一种基本的数据结构，它在计算机科学和编程中有着广泛的应用。与数组不同，链表中的元素不是在内存中连续存储的，而是通过指针连接起来。每个链表节点包含两部分：数据域，用于存储实际的元素值；指针域，...