My_Single_LinkedList
分4个部分实现（CRUD - 增删改查）。
首先要有一个Node（节点类）
class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
instance variables and constructer - 成员变量和构造函数
public Node head; //头指针指向虚拟的node，真正的list是取head.next
public Node last; //尾指针指向最后一个元素
public int length; //list的长度，不是index。在insert的时候，判断insert的index public My_Single_LinkedList() {
this.head = new Node(-1);
this.last = head;
this.length = 0;
}
1. 添加
添加部分有两大部分，一个是添加在头和尾，一个是添加在某个index的左和右。
添加的同时要保持length和last指针的更新
1) 添加在头和尾：O(1)的时间复杂度
public void addLast(int val) {
last.next = new Node(val);
last = last.next;
this.length++;
}
public void addFirst(int val) {
Node newNode = new Node(val);
newNode.next = head.next;
head.next = newNode;
this.length++;
}
2) 在某个index的左和右添加：O(n)时间复杂度
/**
* insert before index
* @param val
* @param index
*/
public void insertBefore(int val, int index) {
if (index <= 0) { //在0之前加，相当于addFirst
addFirst(val);
return;
}
if (index >= length) {//在超出length之前加，相当于addLast
addLast(val);
return;
}
// 普通情况，两个指针，一前一后
Node cur = head.next;
Node prev = head;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
prev = prev.next;
counter++;
}
Node newNode = new Node(val);
newNode.next = cur;
prev.next = newNode;
this.length++;
} /**
* insert after index
* @param val
* @param index certain index you want to insert at
*/
public void insertAfter(int val, int index) {
if (index < 0) {
addFirst(val);
return;
}
if (index >= length - 1) {
addLast(val);
return;
}
Node cur = head.next;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
Node newNode = new Node(val);
newNode.next = cur.next;
cur.next = newNode;
this.length++;
}
2. 更新：O(n)时间复杂度
public void updateAt(int val, int index) {
if (index < 0 || index > length - 1) {
return;
}
int counter = 0;
Node cur = head.next;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
cur.val = val;
}
3. 删除：O(n)时间复杂度
删除的时候也要注意length和last的更新
public void deleteAt(int index) {
if (index < 0 || index > length - 1) {
return;
}
int counter = 0;
Node prev = head;
Node cur = head.next;
while (cur != null && counter < index) {
cur = cur.next;
prev = prev.next;
counter++;
}
prev.next = prev.next.next;
//更新length和last指针
length--;
while (prev.next != null) {
prev = prev.next;
}
this.last = prev;
}
4. 搜索：O(n)时间复杂度
/**
* 根据val搜索
* 返回第一个符合条件node的index
* 如果没有，返回-1
*/
public int getByValue(int val) {
Node cur = head.next;
int index = 0; while (cur != null) {
if (cur.val == val) {
return index;
}
cur = cur.next;
index++;
}
return -1;
} /**
* 根据index搜索
*/
public Node get(int index) {
if (index < 0 || index > length - 1) {
return null;
}
Node cur = head.next;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
return cur;
}
完整代码：
/**
* Created by Mingxiao on 9/5/2016.
*/
public class My_Single_LinkedList { class Node {
public int val;
public Node next; public Node(int val) {
this.val = val;
this.next = null;
}
} public Node head; //头指针指向虚拟的node，真正的list是取head.next
public Node last; //尾指针指向最后一个元素
public int length; //list的长度，不是index。在insert的时候，判断insert的index public My_Single_LinkedList() {
this.head = new Node(-1);
this.last = head;
this.length = 0;
}
// =============== INSERT==========================
public void addLast(int val) {
last.next = new Node(val);
last = last.next;
this.length++;
} public void addFirst(int val) {
Node newNode = new Node(val);
newNode.next = head.next;
head.next = newNode;
this.length++;
} /**
* insert before index
* @param val
* @param index
*/
public void insertBefore(int val, int index) {
if (index <= 0) { //在0之前加，相当于addFirst
addFirst(val);
return;
}
if (index >= length) {//在超出length之前加，相当于addLast
addLast(val);
return;
}
// 普通情况，两个指针，一前一后
Node cur = head.next;
Node prev = head;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
prev = prev.next;
counter++;
}
Node newNode = new Node(val);
newNode.next = cur;
prev.next = newNode;
this.length++;
} /**
* insert after index
* @param val
* @param index certain index you want to insert at
*/
public void insertAfter(int val, int index) {
if (index < 0) {
addFirst(val);
return;
}
if (index >= length - 1) {
addLast(val);
return;
}
Node cur = head.next;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
Node newNode = new Node(val);
newNode.next = cur.next;
cur.next = newNode;
this.length++;
} //===================update=========================
public void updateAt(int val, int index) {
if (index < 0 || index > length - 1) {
return;
}
int counter = 0;
Node cur = head.next;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
cur.val = val;
}
//=====================delete=======================
public void deleteAt(int index) {
if (index < 0 || index > length - 1) {
return;
}
int counter = 0;
Node prev = head;
Node cur = head.next;
while (cur != null && counter < index) {
cur = cur.next;
prev = prev.next;
counter++;
}
prev.next = prev.next.next;
//更新length和last指针
length--;
while (prev.next != null) {
prev = prev.next;
}
this.last = prev;
}
//===================search================================ /**
* 根据val搜索
* 返回第一个符合条件node的index
* 如果没有，返回-1
*/
public int getByValue(int val) {
Node cur = head.next;
int index = 0; while (cur != null) {
if (cur.val == val) {
return index;
}
cur = cur.next;
index++;
}
return -1;
} /**
* 根据index搜索
*/
public Node get(int index) {
if (index < 0 || index > length - 1) {
return null;
}
Node cur = head.next;
int counter = 0;
while (cur != null && counter < index) {
cur = cur.next;
counter++;
}
return cur;
} public void print() {
if (head.next == null) {
System.out.println("null");
return;
}
Node cur = head.next;
while (cur.next != null) {
System.out.print(cur.val + "->");
cur = cur.next;
}
System.out.println(cur.val);
} public static void main(String[] args) {
My_Single_LinkedList list = new My_Single_LinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(0);
list.insertAfter(5,0);
list.updateAt(9, 1);
list.deleteAt(2);
System.out.println(list.get(2).val);
list.print();
}
}