赞
踩
目录
链表是一种在物理存储结构上非连续的存储结构,数据元素的逻辑顺序通过链表中的引用链接次序实现。链表的结构多样,我们通过实现无头单向非循环链表,来进一步理解链表。
从图中可以看出,链表在逻辑上是连续的,但在物理存储结构上不一定是连续的
由于链表是单向的,可以通过前一个节点访问后一个节点,不能通过后一个节点访问前一个结点
要创建链表首先要有节点,我们可以将节点定义为内部类
- public class MySingleList{
- static class ListNode{
- //存放当前结点的值
- private int val;
- //存放下一节点的地址
- private ListNode next;
- public ListNode(){}
- public ListNode(int val){
- this.val = val;
- }
- }
- }
由于链表是通过前一个节点访问下一个节点的,因此我们需要知道链表的第一个节点,因此我们需要定义一个头节点
private ListNode head;//第一个节点
定义变量count用以计算,遍历链表,统计链表节点个数
- //求链表长度
- public int size() {
- int count = 0;
- //定义节点cur,用于遍历链表
- ListNode cur = head;
- while(cur != null){
- count++;
- //指向下一节点
- cur = cur.next;
- }
- return count;
- }
遍历链表,判断节点的值是否等于key
- public boolean contains(int key) {
- ListNode cur = head;
- while(cur != null){
- if(cur.val == key){
- return true;
- }
- cur = cur.next;
- }
- return false;
- }
链表添加元素的方式通常有三种,头插、尾插和在指定位置添加元素。
头插:在链表的第一个节点前插入元素
实现头插,就是让要插入的节点node指向原本链表的头节点head,再更新链表的第一个节点,让head指向新插入的节点
- //头插
- public void addFirst(int data) {
- //创建新节点
- ListNode listNode = new ListNode(data);
- listNode.next = head;
- head = listNode;
- }
尾插:在链表的最后插入元素
实现尾插,首先要找到链表的最后一个节点,再将最后一个节点的next更新为新节点即可
- //尾插
- public void addLast(int data) {
- ListNode newNode = new ListNode(data);
- //若链表为空,直接将head更新为插入节点
- if(head == null){
- head = newNode;
- }else{
- //通过遍历找到最后一个节点
- ListNode cur = head;
- while(cur.next != null){
- cur = cur.next;
- }
- cur.next = newNode;
- }
- }
在指定位置添加元素
在指定位置添加元素,首先要判断指定位置index是否合法,若index < 0 或 index > size,则不能添加元素,然后通过遍历找到节点插入的位置,由于链表为单链表,不能通过后一节点找到前一节点,因此,我们需要找到插入位置的前驱节点,然后通过前驱节点实现链表在index位置的插入
- //在任意位置添加元素
- public void addIndex(int index, int data) {
- //index不正确,无法添加元素
- if(index < 0 || index > size()){
- throw new RuntimeException("输入位置不正确,无法添加元素!");
- }else if(index == 0){//在0位置插入,即为头插
- addFirst(data);
- }else{
- ListNode cur = head;//用cur遍历链表,找到前驱节点
- ListNode listNode = new ListNode(data);
- int count = 0;
- while(count != index-1){
- count++;
- cur = cur.next;
- }
- //添加元素
- listNode.next = cur.next;
- cur.next = listNode;
- }
- }
删除第一个值为key的节点:与在指定位置添加元素相同,我们需要找到第一个值为key的节点node的前驱节点,然后才能删除值为key的节点。由于JVM会将未被任何引用指向的对象回收掉,我们只需让node的前驱节点指向node的下一节点,即可实现删除
- //删除第一个值为key的节点
- public boolean remove(int key) {
- ListNode cur = head;
- //链表第一个节点的值即为key,头删
- if(head.val == key){
- head = head.next;
- return true;
- }//通过遍历找到第一个值为key的节点的前驱节点
- while(cur.next != null){
- if(cur.next.val == key){//找到了,删除节点
- cur.next = cur.next.next;
- return true;
- }
- cur = cur.next;
- }
- return false;//未找到值未key的节点,返回false
- }
删除所有值为key的节点:首先要找到值为key的节点node,将node的上一节点指向node的下一节点,即可删除值为key的节点,注意考虑头节点值为key的情况,要删除链表中所有值为key的节点,利用while循环即可实现。
- //删除所有值为key的节点
- public void removeAllKey(int key) {
- //若链表为空,则直接返回null
- if(head == null){
- return;
- }
- ListNode cur = head;
- while(cur.next != null){
- if(cur.next.val == key){
- cur.next = cur.next.next;
- }else{
- cur = cur.next;
- }
- }
- //单独考虑头节点的值是否等于val
- if(head.val == key){
- head = head.next;
- }
- }
由于JVM会将未被任何引用指向的对象回收掉,清空链表可以将每个节点的指向都置为null,即切断节点之间的链接,也可以直接将head置为null
将每个节点的指向都置为null
- //清空链表
- public void clear() {
- if(head == null){//链表本身为空
- return;
- }
- ListNode cur = head;
- while(cur != null){
- ListNode next = cur.next;//记录下一节点
- cur.next = null;
- cur = next;
- }
- }
直接将head置为null
- //清空链表
- public void clear() {
- head = null;
- }
- public class MySingleList {
- static class ListNode{
- //存放当前结点的值
- private int val;
- //存放下一节点的地址
- private ListNode next;
- public ListNode(){}
- public ListNode(int val){
- this.val = val;
- }
- }
- private ListNode head;//第一个节点
- //求链表长度
- public int size() {
- int count = 0;
- //定义节点cur,用于遍历链表
- ListNode cur = head;
- while(cur != null){
- count++;
- //指向下一节点
- cur = cur.next;
- }
- return count;
- }
- //链表是否包含值为key的节点
- public boolean contains(int key) {
- ListNode cur = head;
- while(cur != null){
- if(cur.val == key){
- return true;
- }
- cur = cur.next;
- }
- return false;
- }
- //头插
- public void addFirst(int data) {
- //创建新节点
- ListNode listNode = new ListNode(data);
- listNode.next = head;
- head = listNode;
- }
- //尾插
- public void addLast(int data) {
- ListNode newNode = new ListNode(data);
- //若链表为空,直接将head更新为插入节点
- if(head == null){
- head = newNode;
- }else{
- //通过遍历找到最后一个节点
- ListNode cur = head;
- while(cur.next != null){
- cur = cur.next;
- }
- cur.next = newNode;
- }
- }
- //在任意位置添加元素
- public void addIndex(int index, int data) {
- //index不正确,无法添加元素
- if(index < 0 || index > size()){
- throw new RuntimeException("输入位置不正确,无法添加元素!");
- }else if(index == 0){//在0位置插入,即为头插
- addFirst(data);
- }else{
- ListNode cur = head;//用cur遍历链表,找到前驱节点
- ListNode listNode = new ListNode(data);
- int count = 0;
- while(count != index-1){
- count++;
- cur = cur.next;
- }
- //添加元素
- listNode.next = cur.next;
- cur.next = listNode;
- }
- }
- //删除第一个值为key的节点
- public boolean remove(int key) {
- ListNode cur = head;
- //链表第一个节点的值即为key,头删
- if(head.val == key){
- head = head.next;
- return true;
- }//通过遍历找到第一个值为key的节点的前驱节点
- while(cur.next != null){
- if(cur.next.val == key){//找到了,删除节点
- cur.next = cur.next.next;
- return true;
- }
- cur = cur.next;
- }
- return false;//未找到值未key的节点,返回false
- }
- //删除所有值为key的节点
- public void removeAllKey(int key) {
- //若链表为空,则直接返回null
- if(head == null){
- return;
- }
- ListNode cur = head;
- while(cur.next != null){
- if(cur.next.val == key){
- cur.next = cur.next.next;
- }else{
- cur = cur.next;
- }
- }
- //单独考虑头节点的值是否等于val
- if(head.val == key){
- head = head.next;
- }
- }
- //清空链表
- public void clear() {
- if(head == null){//链表本身为空
- return;
- }
- ListNode cur = head;
- while(cur != null){
- ListNode next = cur.next;//记录下一节点
- cur.next = null;
- cur = next;
- }
- //或直接将head置为null
- //head = null;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。