链表

模拟链表单链表singleLinkedList有序添加节点的方法删除节点的方法修改节点元素的方法遍历链表节点的方法元素反转的方法元素的逆序打印获取链表长度测试链表

链表是一种常见的基础数据结构,元素是链式的,以节点的形式存储数据元素节点之间不一定是连续的链表可以动态的进行存储分配可以在节点中定义多种数据类型，还可以根据需要随意删除，插入节点链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和普通节点，头结点是没有数据域的链表中普通节点都分为两部分，一个数据域存放数据，一个是指针域指向下一个节点的地址

模拟链表

链表是元素节点组成的数据结构,需要节点类Node节点类Node由两部分组成1.自身数据 string name, int age 2.下一个节点地址 Node next单链表类singleLinkedList属性:头节点自身长度方法:添加节点修改节点删除节点展示所有节点数据逆序打印元素数据反转元素输出单链表中倒数第n个节点

//Node类package linkedList;public class Node {public int number;//编号public String sname;//网名public String sex;//性别public String city;//城市public Node next;//下一个节点public Node() {super();}//初始化public Node(int number, String sname, String sex, String city) {super();this.number = number;this.sname = sname;this.sex = sex;this.city = city;}@Overridepublic String toString() {return "Node [number=" + number + ", sname=" + sname + ", sex=" + sex + ", city=" + city + "]";}}

单链表singleLinkedList

属性:

// 设置头节点private Node head = new Node(0, "", "", "");private int length = 0;// 获取单链表的节点个数,不包括头节点

有序添加节点的方法

按照编号顺序添加元素1.设置辅助变量temp找到添加的位置2.比较编号的大小,新增元素的编码大于所有已存在节点元素的编码,将元素在末尾添加3.新增节点元素编号小于已存在节点的编号,根据temp定位这个节点的前一个节点4.新增节点元素编号等于已存在节点的编号,说明节点编号已经存在,可以选择覆盖或者不添加5.插入节点元素

public void add(Node n) {Node temp = head;boolean flag = false;// 是否添加节点元素的标记值while (true) {// 用temp定位要插入的位置if (temp.next == null) {// 链表末尾任然未找到要插入的位置,直接在末尾添加break;// temp指向链表末尾,在末尾添加元素}if (temp.next.number > n.number) {// 指针的下一个节点的编号大于新增节点编号,位置已经找到break;// 在temp处添加元素} else if (temp.next.number == n.number) {flag = true;// 节点已经存在不用添加节点break;}temp = temp.next;// 指针后移}if (flag) {System.out.println("节点已经存在!");} else {length++;//链表长度+1n.next = temp.next;// 新增节点指向当前节点的下一个节点temp.next = n;// 当前节点指向新增节点}}

删除节点的方法

根据编号删除节点元素,不是真正的删除,只是不会有引用指向这个节点,这个节点就会被回收

public void delNode(int number) {Node temp = head;//临时指针boolean flag = false;// 是否有要删除的节点while (true) {//循环结束之后temp的下一个节点就是要删除的节点if (temp.next == null) {// 链表末尾break;}if (temp.next.number == number) {// 找到要删除的节点flag = true;break;}temp = temp.next;}if (flag) {// 要删除的是temp指向的节点的下一个节点temp.next = temp.next.next;// 跳过要删除的节点length--;} else {System.out.println("未找到要删除的节点！");}}

修改节点元素的方法

根据编号修改节点元素

public void updata(Node n) {if (head.next == null) {//空链表判断System.out.println("空链表！");return;}Node temp = head.next;// 临时指针boolean flag = false;while (true) {//循环结束后temp指向的就是要修改的节点if (temp.number == n.number) {// 找到要修改的节点flag = true;break;}if (temp.next == null) {// 已经到了链表末尾还未找到要修改的节点break;}temp = temp.next;// 指针后移}if (flag) {temp.sname = n.sname;temp.city = n.city;temp.sex = n.sex;} else {System.out.println("节点未找到！");}}

遍历链表节点的方法

public void show() {// 判断链表是否为空if (head.next == null) {System.out.println("空链表!");return;}// 辅助指针Node temp = head.next;while (true) {if (temp.next == null) {// 是否为最后一个节点System.out.println(temp);break;}System.out.println(temp);// 输出节点元素temp = temp.next;// 指针后移}}

元素反转的方法

元素反转会改变链表的整体结构,不推荐使用1.定义一个新链表2.遍历原链表的元素,然后始终添加到新链表的第一个位置,新链表原有元素后移一位就是将这个元素的指针指向新链表原来的第一个元素再将新链表的指针指向这个元素,这个元素就是新链表的第一个元素原来的第一个元素就称为了第二个元素...3.将原链表的引用指向新链表

public void reversetlist() {if (head.next == null || head.next.next == null) {// 空链表或者一个元素的链表不需要反转return;}Node temp = head.next;// 遍历原链表的辅助指针Node nexts = null;// 原链表的下一个节点Node newHeadNode = new Node(0, "", "", "");// 新头节点while (temp != null) {// 当前节点不为空nexts = temp.next;// 当前节点的下一个节点temp.next = newHeadNode.next;// 当前节点指向新链表的第一个节点newHeadNode.next = temp;// 将当前节点添加到新链表的第一个节点上temp = nexts;// 当前节点的下一个节点}head.next = newHeadNode.next;}

元素的逆序打印

将元素逆序输出但是不会改变链表的结构可以利用栈的后进先出的特性完成逆序打印

public void revershow() {if (head.next == null) {// 如果为空链表return;}Stack<Node> stack = new Stack<Node>();Node tempNode = head.next;// 将链表元素入栈while (tempNode != null) {stack.push(tempNode);tempNode = tempNode.next;}// 逆序打印元素while (stack.size() > 0) {System.out.println(stack.pop());//出栈}}

获取链表长度

public int getLength() {/** 这种方式获取的长度有缺陷的,只有以add添加单个节点元素才会增1 只有以del删除单个节点元素才会减1 * 例如新增的节点已经有下一个节点,length就不准* 正确的做法可以遍历链表元素获取长度,但是链表元素过多时不推荐* 或者在进行元素添加时判断新增节点的长度*/return length;}

测试链表

1.创建节点元素2.创建链表元素3.往链表中添加节点4.展示节点

// 创建节点元素Node n1 = new Node(1, "秋叶飞花", "未知", "bj");Node n4 = new Node(4, "春江水暖", "未知", "gz");Node n5 = new Node(5, "暮色", "未知", "hz");Node n3 = new Node(3, "繁花似锦", "女", "sz");Node n2 = new Node(2, "夜色微凉", "男", "sh");Node n6 = new Node(2, "陌上人如玉", "男", "tj");// 创建单链表singleLinkedList linked = new singleLinkedList();linked.add2(n1);// 添加节点元素linked.add2(n4);linked.add2(n5);linked.add2(n3);linked.add2(n2);linked.show();// 显示节点元素//Node [number=1, sname=秋叶飞花, sex=未知, city=bj]//Node [number=2, sname=夜色微凉, sex=男, city=sh]//Node [number=3, sname=繁花似锦, sex=女, city=sz]//Node [number=4, sname=春江水暖, sex=未知, city=gz]//Node [number=5, sname=暮色, sex=未知, city=hz]

链表倒数第n个元素

int index = 4;System.out.println("倒数第" + index + "个节点" + linked.findLastNode(index));// 输出倒数第n个节点//倒数第4个节点Node [number=2, sname=夜色微凉, sex=男, city=sh]