注册一个网站,帮人做违法网站,python+网站开发实例教程,深圳推广优化公司目录
1.链表的基本概念
2.链表的实现 -- 节点的构造和链接 节点如何构造? 如何将链表关联起来?
3.链表的方法(功能)
1).display() -- 链表的遍历
2).size() -- 求链表的长度
3).addFirst(int val) -- 头插法
4).addLast(int val) -- 尾插法
5).addIndex -- 在任意位置…目录
1.链表的基本概念
2.链表的实现 -- 节点的构造和链接 节点如何构造? 如何将链表关联起来?
3.链表的方法(功能)
1).display() -- 链表的遍历
2).size() -- 求链表的长度
3).addFirst(int val) -- 头插法
4).addLast(int val) -- 尾插法
5).addIndex -- 在任意位置插入
6).contains(int val) -- 链表中是否包含某个元素
7). remove(int key) -- 删除第一次出现的关键字的节点
8).removeAll(int val) -- 删除所有出现的关键字的节点
9).clear() -- 清空 回收对象,防止浪费 : head null; 1.链表的基本概念
链表Linked List是一种常见的基础数据结构它由一系列节点Node组成每个节点包含两部分一部分存放数据元素另一部分存放指向下一个节点的指针.
2.链表的实现 -- 节点的构造和链接 节点如何构造? 在 Java 中通常通过定义一个类来表示链表中的节点。每个节点通常包含两个部分数据域和指针域。对于单向链表每个节点的指针域指向下一个节点. public class LinkedList {// 定义链表节点static class ListNode {int val; // 数据域ListNode next; // 指针域ListNode(int x) {this.val x;this.next null;}}public ListNode head;
} 如何将链表关联起来? 通过访问node1的指针域next,将其赋值为下一个节点的地址,以此类推,最后让头节点head指向第一个节点node1. node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;
3.链表的方法(功能)
1).display() -- 链表的遍历 首先我们创建一个名为 cur 的局部变量它是一个指向 ListNode 类型的引用。将链表的头节点head赋值给 cur这样我们就有了一个可以用来遍历整个链表的起始点.使用 while 循环来遍历链表。只要 cur不是 null即还没有到达链表的末尾就继续执行循环体内的代码。如果 cur 是 null则说明已经到了链表的末尾循环结束。在循环体内我们使用 System.out.print 来打印当前节点的数据。这里用 - 格式化输出以箭头分隔各个数据项直观地表示出它们之间的链接关系。更新 cur指针使其指向下一个节点通过 cur.next 获取。这一步非常重要因为它确保了我们在下一次迭代时能够访问链表中的下一个节点。当循环结束后我们额外打印一个 null表示链表的终止。这是为了更清晰地展示链表结构表明没有更多的节点了。 public void display() {ListNode cur head;while(cur ! null) {System.out.print(cur.val -);cur cur.next;}System.out.println(null);}
2).size() -- 求链表的长度 定义count变量,记录cur向后走的次数,每走一步,count public int size() {ListNode cur head;int count 0;while(cur ! null) {count;cur cur.next;}return count;}
3).addFirst(int val) -- 头插法 1. 将head头节点的地址传给node.next 2. 然后让head指向node 注意: 这里两步的顺序不可以交换 , 否则 就是自己指向自己了 public void addFirst(int val) {ListNode node new ListNode(val);node.next head;head node;}
4).addLast(int val) -- 尾插法 1.为了避免head null 报错, 先进行判断,若head null , 则 head node,然后return掉. 2.若head ! null , 则 这通过循环找到 cur.next null ,最后让cur.next node.
public void addLast(int val) {ListNode node new ListNode(val);if(head null) {head node;return;}ListNode cur head;while(cur.next ! null) {cur cur.next;}cur.next node;}
5).addIndex -- 在任意位置插入 1.判断index的合法性: (1). 定义一个 checkIndex(int index) 方法用来检查 index 的合法性 2.index 0 || index size();前者相当于是头插直接调用 addFirst(),后者相当于是尾插直接调用 addLast() 3.找到 index 的前一个位置,创建一个 findIndexSubOne(int index) 方法,创建一个节点 cur 来接收调用方法的返回值, 最后 cur 就是 index 位置的前一个节点了 4.进行连接,实例化一个所带数据为 val 的节点 node, node.next cur.next; cur.next node; public void addIndex(int index,int val) {// 1.判断index的合法性try {checkIndex(index);} catch(IndexNotLegalException e) {e.printStackTrace();}// index 0 || index size()if(index 0) {addFirst(val);return;} else if(index size()) {addLast(val);return;}// 3.找到index前一个位置ListNode cur findIndexSubOne(index);// 4.进行连接ListNode node new ListNode(val);node.next cur.next;cur.next node;}public ListNode findIndexSubOne(int index) {ListNode cur head;for (int i 0; i index - 1; i) {cur cur.next;}return cur;}public void checkIndex(int index) {if(index 0 || index size()) {throw new IndexNotLegalException(index位置不合法);}}public class IndexNotLegalException extends RuntimeException {public IndexNotLegalException() {}public IndexNotLegalException(String message) {super(message);}}
6).contains(int val) -- 链表中是否包含某个元素 遍历链表,如果能在链表中找到val,则返回true,否则,返回false public boolean contains(int val) {ListNode cur head;while(cur ! null) {if(cur.val val) {return true;}cur cur.next;}return false;}
7). remove(int key) -- 删除第一次出现的关键字的节点 1.首先判断链表是否为空 2.循环遍历 : cur.next ! null 3.找到val值的前一个节点cur : 当cur.next.val val 时,找到目标 4.进行删除 public void remove(int key) {// 如果链表为空if(head null) {return;}// 如果第一个元素就为val时if(head.val key) {head head.next;return;}ListNode cur head;while(cur.next ! null) {if(cur.next.val key) {cur.next cur.next.next;return;}cur cur.next;}}
8).removeAll(int val) -- 删除所有出现的关键字的节点 定义两个引用变量 cur 代表当前需要删除的节点prev 代表当前需要删除节点的前驱 若 cur.val val prev.next cur.nextcur cur.next否则 prev curcur cur.next处理头节点 public void removeAll(int key) {if(head null) {return;}ListNode prev head;ListNode cur head.next;while(cur ! null) {if(cur.val key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}// 除了头节点都删除完成if(head.val key) {head head.next;}}
9).clear() -- 清空 回收对象,防止浪费 : head null;
public void clear() {this.head null;}
