大部分記錄均來自小灰漫畫算法
-
什么是鏈表？
物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)萤彩。由若干節(jié)點(diǎn)組成。
鏈表.png - 鏈表的基本操作
①查找節(jié)點(diǎn)：只能從頭節(jié)點(diǎn)開始向后一個(gè)節(jié)點(diǎn)逐一查找斧拍。
第一步：將查找的指針定位到頭節(jié)點(diǎn)雀扶；
第二步：根據(jù)頭節(jié)點(diǎn)的next指針，定位到第二個(gè)節(jié)點(diǎn)肆汹；
第三布：根據(jù)第二個(gè)節(jié)點(diǎn)的next指針愚墓，定位到第三個(gè)節(jié)點(diǎn)。依次類推昂勉。
②更新節(jié)點(diǎn)：不考慮查找的情況下浪册，直接舊數(shù)據(jù)替換成新數(shù)據(jù)即可。
③插入節(jié)點(diǎn)： - 頭部插入
第一步：新節(jié)點(diǎn)的Next指針指向原先的頭節(jié)點(diǎn)
第二步：新節(jié)點(diǎn)變?yōu)殒湵淼念^節(jié)點(diǎn) - 尾部插入
最后一個(gè)節(jié)點(diǎn)的next指向新插入節(jié)點(diǎn)即可 - 中間插入
第一步：新節(jié)點(diǎn)的Next指針岗照，指向插入位置的節(jié)點(diǎn)村象；
第二部：插入位置的前置節(jié)點(diǎn)next指針笆环，指向新節(jié)點(diǎn)。
④刪除節(jié)點(diǎn)： - 頭部刪除
鏈表頭節(jié)點(diǎn)設(shè)置為原先頭節(jié)點(diǎn)的next指針 - 尾部刪除
指向最后一個(gè)元素的Next指針厚者，置為Null即可 - 中間刪除
刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)的Next指針躁劣，指向要?jiǎng)h除元素的下一個(gè)節(jié)點(diǎn)即可。
//記錄鏈表的長度
private int size = 0;
//頭尾指針
private Node head;
private Node last;
/**
* 插入元素
* @param data：插入元素
* @param index：插入位置(從0開始)
*/
public void insert(int data,int index){
//TODO:判斷插入位置
if(index < 0 && index > size) {
throw new IndexOutOfBoundsException("超出鏈表范圍");
}
//TODO:創(chuàng)建要插入的元素
Node node = new Node(data);
//TODO:插入位置判斷(頭部库菲，尾部账忘，中間)
if(size == 0) {//創(chuàng)建一個(gè)鏈表
head = last = node;
}else if(index == 0) {
node.next = head;
head = node;
}else if(index == size) {
last.next = node;
last = node;
}else{
Node preNode = findNode(index - 1);
node.next = preNode.next;
preNode.next = node;
}
//TODO:插入后鏈表長度加1
size++;
}
/**
* 根據(jù)位置查找對(duì)應(yīng)的節(jié)點(diǎn)
* @param index：查找的位置
* @return：查詢結(jié)果
*/
public Node findNode(int index){
//TODO:判斷查詢位置是否合法
if(index < 0 && index > size) {
throw new IndexOutOfBoundsException("超出鏈表查詢范圍");
}
//TODO:頭節(jié)點(diǎn)開始逐一向后一節(jié)點(diǎn)查找
if(size == 0) {
throw new IndexOutOfBoundsException("暫無鏈表");
}else{
Node node = head;
for (int pos = 0 ; pos < index ; pos++){
node = node.next;
}
return node;
}
}
/**
* 根據(jù)位置跟新節(jié)點(diǎn)
* @param index
* @param node
*/
public void updateNode(int index,Node node){
//TODO:判斷查詢位置是否合法
if(index < 0 && index > size) {
throw new IndexOutOfBoundsException("超出鏈表查詢范圍");
}
if(size == 0) {
throw new IndexOutOfBoundsException("暫無鏈表");
}else{
Node findNode = findNode(index);
findNode.data = node.data;
}
}
/**
* 刪除元素
* @param index
*/
public void deleteNode(int index){
//TODO:判斷查詢位置是否合法
if(index < 0 && index > size) {
throw new IndexOutOfBoundsException("超出鏈表查詢范圍");
}
if(size == 0) {
throw new IndexOutOfBoundsException("暫無鏈表");
}else{
Node node = findNode(index);
if(index == 0) {
head = node.next;
}else if(index == size - 1) {
node.next = null;
}else{
Node preNode = findNode(index - 1);
preNode.next = node.next;
}
//TODO:插入后鏈表長度減1
size--;
}
}
//包含元素跟指針
private static class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public void output(){
Node node = head;
if(node != null) {
for (int i = 0 ; i < size ; i++){
System.out.println("Node : " + node.data);
node = node.next;
}
}
}
public static void main(String [] args){
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.insert(3,0);
myLinkedList.insert(5,1);
myLinkedList.insert(7,2);
myLinkedList.insert(9,3);
myLinkedList.insert(1,1);
myLinkedList.output();
myLinkedList.deleteNode(0);
myLinkedList.deleteNode(2);
myLinkedList.output();
}
總結(jié)；鏈表再刪除和插入方面效率遠(yuǎn)高于更新跟查找
