链接列表插入删除方法
链接列表插入方法使我们可以在特定位置插入Node。
根据插入新节点的位置，有三种插入方法。
- addLast
- addFirst
- addAt
链接列表插入方法
顾名思义，新节点将附加在"链接"列表的最后一个位置。
链接列表的大小增加1。
" tail"指向新添加的Node。
由于我们有尾节点，因此时间复杂度为O(1)，否则为O(n)。
1. addLast
新节点将添加到"链接"列表的第一个位置。
链接列表的大小增加1。
" head"指向新添加的Node。
由于不涉及List的遍历，因此时间复杂度为O(1)。
2. addFirst
此方法有两个参数-要插入的Node和一个整数索引(例如" k")。
该节点将添加到"链接"列表的第k个位置。
链接列表的大小增加1。
如果要添加的元素是" First"或者" Last"，则分别调用" addFirst"或者" addLast"。
在此操作中，我们还使用另一个函数" getNodeAt"，它是我们的链接列表类的私有成员。
此函数将整数索引作为参数，如果索引有效(即，如果index> = 0且index <链接列表的大小)，则它将返回该索引处的Node。
因此，在此功能中，需要遍历链接列表。
addAt()函数的时间复杂度为O(n)。
3. addAt
链接列表删除
链表支持三种删除节点的方法。
- removeLast
- removeFirst
- removeAt
链接列表删除方法
此方法删除链接列表的最后一个元素(提供的列表不是一个空列表，它会引发异常)。
它将"尾巴"移动到最后一个第二个元素(如果有的话)，并将大小减小" 1"。
同样，它返回删除的数据。
由于我们有尾节点，因此时间复杂度为O(1)，否则为O(n)。
1.删除最后
它将删除"链接"列表的第一个元素(如果列表不是空列表，则其中引发异常)。
此方法将" head"移至第二个元素(如果有的话)，并将大小减小" 1"。
同样，它返回删除的数据。
由于不涉及List的遍历，因此时间复杂度为O(1)。
2. removeFirst
它使用一个整数索引(假设为k)作为参数，如果索引有效，它将删除"链接"列表的" kth"元素并将其大小减小" 1"。
同样，它返回删除的数据。
如果要删除的元素是" First"或者" Last"，则分别调用" removeFirst"或者" removeLast"。
在此操作中，我们还使用另一个函数" getNodeAt"，它是链接列表类的私有成员。
此函数将整数索引作为参数，如果索引有效(即，如果index> = 0且index <链接列表的大小)，则它将返回该索引处的Node。
因此，在该函数中，需要遍历列表，因此，它是O(n)，这会使操作" removeAt"的时间复杂度变为O(n)。
3. removeAt
package com.theitroad.ds;
public class LinkedList1 {
private class Node {
int data;
Node next;
}
private Node head;
private Node tail;
private int size;
public int size() {
return this.size;
}
public int getFirst() throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
return this.head.data;
}
public int getLast() throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
return this.tail.data;
}
public int getAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
Node temp = this.head;
for (int i = 1; i <= idx; i++) {
temp = temp.next;
}
return temp.data;
}
private Node getNodeAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
Node temp = this.head;
for (int i = 1; i <= idx; i++) {
temp = temp.next;
}
return temp;
}
public void addLast(int item) {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
if (this.size > 0)
this.tail.next = nn;
//dm update
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size += 1;
} else {
this.tail = nn;
this.size += 1;
}
}
public void addFirst(int item) {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
nn.next = this.head;
//dm update
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size++;
} else {
this.head = nn;
this.size++;
}
}
public void addAt(int item, int idx) throws Exception {
if (idx < 0 || idx > this.size) {
throw new Exception("Invalid Index.");
}
if (idx == 0) {
addFirst(item);
} else if (idx == this.size) {
addLast(item);
} else {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
Node nm1 = getNodeAt(idx - 1);
Node np1 = nm1.next;
nm1.next = nn;
nn.next = np1;
//dm
this.size++;
}
}
public int removeFirst() throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
Node temp = this.head;
if (this.size == 1) {
this.head = null;
this.tail = null;
this.size = 0;
} else {
this.head = this.head.next;
this.size--;
}
return temp.data;
}
public int removeLast() throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
Node temp = this.tail;
if (this.size == 1) {
this.head = null;
this.tail = null;
this.size = 0;
} else {
Node sm2 = getNodeAt(this.size - 2);
sm2.next = null;
this.tail = sm2;
this.size--;
}
return temp.data;
}
public int removeAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
if (idx == 0) {
return removeFirst();
} else if (idx == this.size - 1) {
return removeLast();
} else {
Node nm1 = getNodeAt(idx - 1);
Node n = nm1.next;
Node np1 = n.next;
nm1.next = np1;
this.size--;
return n.data;
}
}
public void display() {
System.out.println("----------------------");
Node temp = this.head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println(".");
System.out.println("----------------------");
}
public static void main(String[] args) throws Exception {
LinkedList1 list = new LinkedList1();
list.addLast(10);
list.addLast(20);
list.addLast(30);
list.addLast(40);
//this will display the list
list.display();
//10 should be removed and printed
System.out.println(list.removeFirst());
list.display();
//40 should be removed and printed
System.out.println(list.removeLast());
list.display();
//list without 10 and 40 should be printed
list.display();
//100 should be added at first
list.addFirst(100);
list.display();
//30 should be removed
list.removeAt(2);
list.display();
//300 should be added at 2nd index
list.addAt(300, 2);
list.display();
}
}
