单向链表
单向循环链表
注意:
构造函数名不带泛型
链表 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;
单向链表是一种基本的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的引用。在计算机科学中,链表常用于构建动态数据结构,因为它们允许高效的插入和删除操作,尤其是在元素的位置未知时。而基...
单向链表是一种基本的数据结构,它在计算机科学和编程中有着广泛的应用。与数组不同,链表中的元素不是在内存中连续存储的,而是通过指针连接起来。每个链表节点包含两部分:数据域,用于存储实际的元素值;指针域,...