首页 > 代码库 > 自己实现Single LinkedList
自己实现Single LinkedList
My_Single_LinkedList
分4个部分实现（CRUD - 增删改查）。
首先要有一个Node（节点类）
1 class Node {2 public int val;3 public Node next;4 5 public Node(int val) {6 this.val = val;7 this.next = null;8 }9 }
instance variables and constructer - 成员变量和构造函数
1 public Node head; //头指针指向虚拟的node，真正的list是取head.next2 public Node last; //尾指针指向最后一个元素3 public int length; //list的长度，不是index。在insert的时候，判断insert的index4 5 public My_Single_LinkedList() {6 this.head = new Node(-1);7 this.last = head;8 this.length = 0;9 }
1. 添加
添加部分有两大部分，一个是添加在头和尾，一个是添加在某个index的左和右。
添加的同时要保持length和last指针的更新
1) 添加在头和尾：O(1)的时间复杂度
1 public void addLast(int val) { 2 last.next = new Node(val); 3 last = last.next; 4 this.length++; 5 } 6 7 public void addFirst(int val) { 8 Node newNode = new Node(val); 9 newNode.next = head.next;10 head.next = newNode;11 this.length++;12 }
2) 在某个index的左和右添加：O(n)时间复杂度
1 /** 2 * insert before index 3 * @param val 4 * @param index 5 */ 6 public void insertBefore(int val, int index) { 7 if (index <= 0) { //在0之前加，相当于addFirst 8 addFirst(val); 9 return;10 }11 if (index >= length) {//在超出length之前加，相当于addLast12 addLast(val);13 return;14 }15 // 普通情况，两个指针，一前一后16 Node cur = head.next;17 Node prev = head;18 int counter = 0;19 while (cur != null && counter < index) {20 cur = cur.next;21 prev = prev.next;22 counter++;23 }24 Node newNode = new Node(val);25 newNode.next = cur;26 prev.next = newNode;27 this.length++;28 }29 30 /**31 * insert after index32 * @param val33 * @param index certain index you want to insert at34 */35 public void insertAfter(int val, int index) {36 if (index < 0) {37 addFirst(val);38 return;39 }40 if (index >= length - 1) {41 addLast(val);42 return;43 }44 Node cur = head.next;45 int counter = 0;46 while (cur != null && counter < index) {47 cur = cur.next;48 counter++;49 }50 Node newNode = new Node(val);51 newNode.next = cur.next;52 cur.next = newNode;53 this.length++;54 }
2. 更新：O(n)时间复杂度
1 public void updateAt(int val, int index) { 2 if (index < 0 || index > length - 1) { 3 return; 4 } 5 int counter = 0; 6 Node cur = head.next; 7 while (cur != null && counter < index) { 8 cur = cur.next; 9 counter++;10 }11 cur.val = val;12 }
3. 删除：O(n)时间复杂度
删除的时候也要注意length和last的更新
1 public void deleteAt(int index) { 2 if (index < 0 || index > length - 1) { 3 return; 4 } 5 int counter = 0; 6 Node prev = head; 7 Node cur = head.next; 8 while (cur != null && counter < index) { 9 cur = cur.next;10 prev = prev.next;11 counter++;12 }13 prev.next = prev.next.next;14 //更新length和last指针15 length--;16 while (prev.next != null) {17 prev = prev.next;18 }19 this.last = prev;20 }
4. 搜索：O(n)时间复杂度
1 /** 2 * 根据val搜索 3 * 返回第一个符合条件node的index 4 * 如果没有，返回-1 5 */ 6 public int getByValue(int val) { 7 Node cur = head.next; 8 int index = 0; 9 10 while (cur != null) {11 if (cur.val == val) {12 return index;13 }14 cur = cur.next;15 index++;16 }17 return -1;18 }19 20 /**21 * 根据index搜索22 */23 public Node get(int index) {24 if (index < 0 || index > length - 1) {25 return null;26 }27 Node cur = head.next;28 int counter = 0;29 while (cur != null && counter < index) {30 cur = cur.next;31 counter++;32 }33 return cur;34 }
完整代码：
1 /** 2 * Created by Mingxiao on 9/5/2016. 3 */ 4 public class My_Single_LinkedList { 5 6 class Node { 7 public int val; 8 public Node next; 9 10 public Node(int val) { 11 this.val = val; 12 this.next = null; 13 } 14 } 15 16 public Node head; //头指针指向虚拟的node，真正的list是取head.next 17 public Node last; //尾指针指向最后一个元素 18 public int length; //list的长度，不是index。在insert的时候，判断insert的index 19 20 public My_Single_LinkedList() { 21 this.head = new Node(-1); 22 this.last = head; 23 this.length = 0; 24 } 25 // =============== INSERT========================== 26 public void addLast(int val) { 27 last.next = new Node(val); 28 last = last.next; 29 this.length++; 30 } 31 32 public void addFirst(int val) { 33 Node newNode = new Node(val); 34 newNode.next = head.next; 35 head.next = newNode; 36 this.length++; 37 } 38 39 /** 40 * insert before index 41 * @param val 42 * @param index 43 */ 44 public void insertBefore(int val, int index) { 45 if (index <= 0) { //在0之前加，相当于addFirst 46 addFirst(val); 47 return; 48 } 49 if (index >= length) {//在超出length之前加，相当于addLast 50 addLast(val); 51 return; 52 } 53 // 普通情况，两个指针，一前一后 54 Node cur = head.next; 55 Node prev = head; 56 int counter = 0; 57 while (cur != null && counter < index) { 58 cur = cur.next; 59 prev = prev.next; 60 counter++; 61 } 62 Node newNode = new Node(val); 63 newNode.next = cur; 64 prev.next = newNode; 65 this.length++; 66 } 67 68 /** 69 * insert after index 70 * @param val 71 * @param index certain index you want to insert at 72 */ 73 public void insertAfter(int val, int index) { 74 if (index < 0) { 75 addFirst(val); 76 return; 77 } 78 if (index >= length - 1) { 79 addLast(val); 80 return; 81 } 82 Node cur = head.next; 83 int counter = 0; 84 while (cur != null && counter < index) { 85 cur = cur.next; 86 counter++; 87 } 88 Node newNode = new Node(val); 89 newNode.next = cur.next; 90 cur.next = newNode; 91 this.length++; 92 } 93 94 //===================update========================= 95 public void updateAt(int val, int index) { 96 if (index < 0 || index > length - 1) { 97 return; 98 } 99 int counter = 0;100 Node cur = head.next;101 while (cur != null && counter < index) {102 cur = cur.next;103 counter++;104 }105 cur.val = val;106 }107 //=====================delete=======================108 public void deleteAt(int index) {109 if (index < 0 || index > length - 1) {110 return;111 }112 int counter = 0;113 Node prev = head;114 Node cur = head.next;115 while (cur != null && counter < index) {116 cur = cur.next;117 prev = prev.next;118 counter++;119 }120 prev.next = prev.next.next;121 //更新length和last指针122 length--;123 while (prev.next != null) {124 prev = prev.next;125 }126 this.last = prev;127 }128 //===================search================================129 130 /**131 * 根据val搜索132 * 返回第一个符合条件node的index133 * 如果没有，返回-1134 */135 public int getByValue(int val) {136 Node cur = head.next;137 int index = 0;138 139 while (cur != null) {140 if (cur.val == val) {141 return index;142 }143 cur = cur.next;144 index++;145 }146 return -1;147 }148 149 /**150 * 根据index搜索151 */152 public Node get(int index) {153 if (index < 0 || index > length - 1) {154 return null;155 }156 Node cur = head.next;157 int counter = 0;158 while (cur != null && counter < index) {159 cur = cur.next;160 counter++;161 }162 return cur;163 }164 165 public void print() {166 if (head.next == null) {167 System.out.println("null");168 return;169 }170 Node cur = head.next;171 while (cur.next != null) {172 System.out.print(cur.val + "->");173 cur = cur.next;174 }175 System.out.println(cur.val);176 }177 178 179 public static void main(String[] args) {180 My_Single_LinkedList list = new My_Single_LinkedList();181 list.addLast(1);182 list.addLast(2);183 list.addLast(0);184 list.insertAfter(5,0);185 list.updateAt(9, 1);186 list.deleteAt(2);187 System.out.println(list.get(2).val);188 list.print();189 }190 }
自己实现Single LinkedList
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。