那个网站做外贸最好,深圳软件开发公司在哪里,传媒公司 网站开发,软件开发工程师是什么职业LinkedList的模拟实现#xff08;底层是一个双向链表#xff09;LinkedList使用 LinkedList的模拟实现#xff08;底层是一个双向链表#xff09;
无头双向链表#xff1a;有两个指针#xff1b;一个指向前一个节点的地址#xff1b;一个指向后一个节点的地址。 节点定… LinkedList的模拟实现底层是一个双向链表LinkedList使用 LinkedList的模拟实现底层是一个双向链表
无头双向链表有两个指针一个指向前一个节点的地址一个指向后一个节点的地址。 节点定义和链表初始化
class ListNode{int val;ListNode prev;ListNode next;public ListNode(int val) {this.val val;}}ListNode head;ListNode tail;public void createList(){//初始化链表
ListNode ListNode1new ListNode(1);ListNode ListNode2new ListNode(1);ListNode ListNode3new ListNode(1);ListNode ListNode4new ListNode(1);ListNode ListNode5new ListNode(1);ListNode ListNode6new ListNode(1);ListNode1.nextListNode2;ListNode2.nextListNode3;ListNode3.nextListNode4;ListNode4.nextListNode5;ListNode5.nextListNode6;//还要绑定prevListNode6 ListNode5.prev;ListNode5 ListNode4.prev;ListNode4 ListNode3.prev;ListNode3 ListNode2.prev;ListNode2 ListNode1.prev;tailListNode6;//指向尾节点this.headListNode1;
}打印链表 public void myprintf(){ListNode curhead;while(cur!null){System.out.println(cur.val);curcur.next;}}头插法分两种情况1有多个节点需要修改3个地方2没有节点的时候插入。tail是我们定义的尾巴 1head指向 2原来头节点的null位置指向 3插入的这个节点的next域 //头插法public void addFirst(int data) {ListNode node new ListNode(data);if (head null) {//空链表的情况下头插head node;tail node;} else {//首先我们知道3个东西需要修改改之前好好想一下这个东西还有没有作用如果有你就不能先改或者把值存起来node.next head;head.prev node;head node;}}尾插法和头插差不多也是分两种情况1空链表2有多个节点情况需要修改3个地方 //尾插法public void addLast(int data){ListNode node new ListNode(data);if (head null) {//空链表的情况下尾插情况一样head node;tail node;} else {//这时候我们的指向尾的指针就有用了tail.nextnode;node.prevtail.prev;tailnode;//尾插后尾得更新一下这个容易忘}}任意位置插入分空链表单独处理和多个节点需要先遍历找到位置需要修改4个指向。我们需要判断一下插入的位置合法不合法 //任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//index位置合法性ListNode node new ListNode(data);if (head null) {//空链表的情况下尾插情况一样head node;tail node;return true;}if(index0||indexsize()){System.out.println(插入的位置不合法);return false;}if(index0){//头插addFirst( data);return true;}if(indexsize()) {//尾插addLast (data);return true;}ListNode cur1select( index);node.nextcur1;//前驱节点我不知道怎么表示//prev指向前驱的地址前驱地址又可以.prev/.next//cur1.prev.next cur1.prev找到前一个的地址cur1.prev.nextnode;node.prevcur1.prev;cur1.prevnode;return true;}找位置 public ListNode select(int index){ListNode curhead;while(index0){curcur.next;}return cur;}删除第一次出现值为key节点 我们先不考虑头尾先考虑中间情况
前驱的next等于当前的next跳过中间
cur.next前驱等于cur前驱 算上头尾情况的整体代码 上述代码还不够只有一个节点的情况lhead.prev;没有前驱空指针异常都没有前驱上述代码还要找前驱在第7行代码还得再套一层娃
清除函数 为什么单向链表清除能直接headnull而双向链表不能headnull、tailnull缺不行 理论上单向链表也是要将所有的节点都置为null双向链表为了更好1及时释放内存空间就是正常情况下headnull和tailnull它的中间节点也是会被垃圾回收器回收的
LinkedList使用 带参数构造方法实现这个接口的都可以传进来顺序表实现了这个接口所以把顺序表传过去也行链表顺序表add都是默认尾插的。 foreach遍历 迭代器遍历 反向遍历 ArrysList和LinkedList区别 增删改查上、储存上呢
