网站建设合同图表版,wordpress放视频教程,橙 网站,电子商务网站开发与设计项目管理文章目录 LinkedList笔记一、 LinkedList1.概念2.LinkedList的构造方法3.LinkedList的遍历 二、MyLinkedList的实现1.定义内部类2.打印链表、求链表长度、判断是否包含关键字3. 头插法和尾插法4.在任意位置插入5.删除结点6.清空链表 LinkedList笔记 一、 LinkedList
1.概念
L… 文章目录 LinkedList笔记一、 LinkedList1.概念2.LinkedList的构造方法3.LinkedList的遍历 二、MyLinkedList的实现1.定义内部类2.打印链表、求链表长度、判断是否包含关键字3. 头插法和尾插法4.在任意位置插入5.删除结点6.清空链表 LinkedList笔记 一、 LinkedList
1.概念
LinkedList的底层是一个双向链表
在插入和删除时不用挪动元素在获取尾部结点时不需要遍历获取直接利用last结点
2.LinkedList的构造方法
分为无参构造和有参构造 有参使用其他集合容器中元素构造List 在构造LinkedList的时候传递的参数的类型要满足指定泛型的上界同时要实现Collection接口 3.LinkedList的遍历
分别用重写的print方法、foreach、迭代器进行遍历 public static void main(String[] args) {LinkedListString linkedList new LinkedList();linkedList.add(hello);linkedList.add(world);linkedList.add(!);linkedList.add(?);linkedList.add(|);System.out.println(linkedList);System.out.println(-----------);for (String x:linkedList) {System.out.print(x );}System.out.println();System.out.println(-----------);//使用迭代器遍历-正向遍历ListIteratorString it linkedList.listIterator();while (it.hasNext()){System.out.print(it.next() );}System.out.println();System.out.println();ListIteratorString rit linkedList.listIterator(linkedList.size());while (rit.hasPrevious()){System.out.print(rit.previous() );}//使用迭代器遍历-反向遍历}二、MyLinkedList的实现
1.定义内部类
与单链表不同的是双链表的结点新增了prev域
public class MyLinkedList {static class ListNode{public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {//构造方法this.val val;}}public ListNode head;//定义头结点public ListNode last;//定义尾结点 1.在内部类中定义结点的元素 2.定义构造器 3.创建头/尾结点 2.打印链表、求链表长度、判断是否包含关键字
与单链表的形式相同 public void disPlay(){ListNode cur head;while (cur!null){ System.out.print(cur.val );cur cur.next;}System.out.println();}/***求链表长度* return int*/public int size(){ListNode cur head;int count 0;while (cur!null){count;cur cur.next;}return count;}/*** 查看在链表中是否包含关键字key* param key* return*/public boolean contains(int key){ListNode cur head;while (cur ! null){if (cur.val key){return true;}cur cur.next;}return false;}3. 头插法和尾插法 /*** 头插法* o(1)* param data*/public void addFirst(int data){ListNode node new ListNode(data);if (head null){head node;last node;}else {node.next head;head.prev node;head node;//头结点前移}}/*** 尾插法o(1)*/public void addLast(int data){ListNode node new ListNode(data);if(headnull){head node;last node;}else{last.next node;node.prev last;last node;}} 因为尾插的时候有last结点不用进行尾结点的遍历查找 所以双链表尾插的时间复杂度是 o1 4.在任意位置插入 public void addIndex(int index, int data) {if (index 0 || index size()) {//判断索引是否超出return;}if (index 0) {//利用头插addFirst(data);return;}if (index size()) {//利用尾插addLast(data);return;}ListNode node new ListNode(data);ListNode cur head;while (index!0){//找到索引的位置cur cur.next;index--;}node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}1.先判断索引下标是否溢出 2.如果索引是开头或者末尾的位置调用写好的头插法和尾插法 3.通过遍历找到索引的位置cur 4.将cur插入链表中 先改变node的next域将node与cur相连 将cur的前驱的next域改为node,将node与cur的前一个结点相连将node前驱改为cur前驱的地址 将cur的前驱改为node的地址值 5.删除结点 public void remove(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {if (cur head) {//删的是头的情况head head.next;if (head!null){//如果只有一个结点移动后前驱不需要置空head.prev null;//head的前驱置为空}} else {//删除中间或者尾部cur.prev.next cur.next;if (cur last) {//如果是尾部last last.prev;} else {//删除的是中间cur.next.prev cur.prev;}}return;}cur cur.next;}}1.通过遍历找到值等于key的结点 2.如果要删的是头结点头结点向后移动一位。如果移动后的头结点不为空将此时头结点的前驱置为空 3.如果要删除的cur是尾结点将cur前驱的地址值指向cur的下一个地址将last向前移动一位 4.如果要删除的是中间结点将cur前驱的地址值指向cur的下一个地址将cur后继的前驱指向cur的前驱 6.清空链表 public void clear() {ListNode cur head;while (cur ! null) {ListNode curNext cur.next;cur.next null;cur.prev null;cur curNext;}head null;last null;}1.遍历链表用curNext记录cur的下一个结点 2.将cur的前驱和后继置为null 3.将头结点和尾结点置为空。 点击移步博客主页欢迎光临~
