杭州网站建设优化推广,山东网站建设公司哪家好,西安官网seo哪家公司好,钦州做网站的公司链表的概念
学过ArrayList后我们知道它的底层是用数组来存储元素的#xff0c;是连续的存储空间#xff0c;当我们要从ArrayList任意位置删除或插入元素时#xff0c;我们要把后续整体向前或后移动#xff0c;时间复杂度为O(n)#xff0c;效率比较低#xff0c;因此Arra…链表的概念
学过ArrayList后我们知道它的底层是用数组来存储元素的是连续的存储空间当我们要从ArrayList任意位置删除或插入元素时我们要把后续整体向前或后移动时间复杂度为O(n)效率比较低因此ArrayList不适合做需要过多任意位置插入或删除的场景这种场景我们使用LinkedList链表比较合适。 链表的一个节点分为值域存储的是节点的值和指针域存储的是下一个节点的地址链表的逻辑顺序是连续的但物理地址不一定是连续的因为节点是从堆中申请出来的从堆中申请的空间是按照一定的策略分配的两次申请的空间可能是连续的也有可能不连续。
模拟实现无头单向非循环链表
//无头单向非循环链表实现
public class SingleLinkedList {static class ListNode{public int val;//节点值域public ListNode next;//节点指针域 下一个节点的地址public ListNode(int val) {this.val val;}}ListNode head;//当前链表的头节点//初始化一个简单的链表public void createList(){ListNode node1 new ListNode(11);ListNode node2 new ListNode(22);ListNode node3 new ListNode(33);ListNode node4 new ListNode(44);ListNode node5 new ListNode(55);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;}
}链表常用的方法
//头插法
public void addFirst(int data)//尾插法
public void addLast(int data)//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)//查找是否包含关键字key是否在单链表当中
public boolean contains(int key)//删除第一次出现关键字为key的节点
public void remove(int key)//删除所有值为key的节点
public void removeAllKey(int key)//得到单链表的长度
public int size()//清除链表
public void clear()实现addFirst方法头插法
public void addFirst(int data) {ListNode node new ListNode(data);//让要插入的节点的指针域指向头节点node.next head;//让插入的节点成为头节点head node;
}实现addList方法尾插法
要实现尾插法我们就必须要找到最后一个节点所以我们要遍历链表遍历链表的时候我们可以定义一个节点指向头节点然后让定义的节点向后去遍历链表
public void addLast(int data) {ListNode node new ListNode(data);//定义一个节点cur指向头节点ListNode cur head;//判断链表是否为空 如果为空就直接插入if (curnull){head node;return;}//遍历链表找到最后一个节点while (cur.next!null){cur cur.next;}//插入节点cur.next node;
}实现size方法获取链表的长度
public int size() {//定义一个变量来记录链表长度int count 0;ListNode cur head;//遍历链表while (cur!null){count;cur cur.next;}return count;
}实现addIndex方法在任意位置插入元素
public void addIndex(int index, int data) {//判断要插入的位置是否合法if (index0||indexsize()){System.out.println(index 不合法index);return;}//index为0 我们使用头插if (index0){addFirst(data);return;}//index等于链表的长度我们可以使用尾插if (indexsize()){addLast(data);return;}ListNode node new ListNode(data);ListNode cur head;for (int i 0; i index-1; i) {cur cur.next;}node.next cur.next;cur.next node;
}实现contains方法查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {ListNode cur head;//如果链表为空直接返回falsewhile (cur!null){//判断是否是key 是返回true 不是则遍历下一个节点if (cur.valkey){return true;}cur cur.next;}return false;
}实现remove方法删除第一次出现关键字为key的节点
我们可以先定义一个方法查看key是否在链表中
private ListNode searchKey(int key){ListNode cur head;while (cur.next!null){//判断cur是否是要删除节点的前一个节点if (cur.next.valkey){return cur;}cur cur.next;}return null;
}public void remove(int key) {//判断链表是否为空if (headnull){return;}//判断头节点是否为要删除的节点if (head.valkey){head head.next;return;}//查找key是否在链表中 不在则返回nullListNode cur searchKey(key);if (curnull){System.out.println(没有key的节点key);return;}//因为cur是要删除节点的前一个节点 所以cur.next才是要删除的节点ListNode del cur.next;cur.next del.next;
}实现removeAllKey方法删除所有值为key的节点
public void removeAllKey(int key) {//判断链表是否为空if (headnull){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.valkey){head head.next;}
}实现clear方法清除链表
//只需将头节点置为空即可
public void clear() {head null;
}
