Методы вставки и удаления Связанного списка

Методы Вставки Связанного списка

Методы вставки связанного списка позволяют нам вставлять узел в определенное место. Существует три метода вставки, основанных на положении, в которое вставляется новый узел.

addLast
Добавить сначала
добавить

1. добавьте Последнее

Как следует из названия, новый узел добавляется в последнюю позицию связанного списка. Размер связанного списка увеличивается на 1. “Хвост” указывает на недавно добавленный узел. Поскольку у нас есть хвостовой узел, временная сложность составляет O(1), иначе это было бы O(n).

2. добавьте Сначала

Новый узел добавляется в первую позицию связанного списка. Размер связанного списка увеличивается на 1. “Голова” указывает на недавно добавленный узел. Временная сложность составляет O(1), так как обход списка не требуется.

3. добавьте В

Этот метод имеет два аргумента – вставляемый узел и целочисленный индекс (скажем, “k”). Узел добавляется в k-ю позицию связанного списка. Размер связанного списка увеличивается на 1.

В случае, если добавляемый элемент является “Первым” или “Последним”, он вызывает “добавить первым” или “Добавить последним” соответственно.

В этой операции мы также используем другую функцию “getNodeAt”, которая является закрытым членом нашего класса Связанного списка. Эта функция принимает в качестве аргумента целочисленный индекс, и если индекс допустим (т. Е. Если и индекс <размер связанного списка), она возвращает узел с этим индексом.

Таким образом, в этой функции требуется обход связанного списка. Временная сложность функции addAt() равна O(n).

Методы удаления Связанного списка

Удалить Связанный список

Связанный список поддерживает три метода удаления узлов.

Удалить последние
Удалить первым
удалить

1. удалите Последнюю

Этот метод удаляет последний элемент связанного списка (при условии, что список не является пустым списком, в котором он создает исключение). Он перемещает “хвост”, указывая на 2-й последний элемент (если таковой имеется), и уменьшает размер на “1”. Кроме того, он возвращает удаленные данные. Поскольку у нас есть хвостовой узел, следовательно, временная сложность составляет O(1), иначе это было бы O(n).

2. сначала удалите

Он удаляет первый элемент связанного списка (при условии, что список не является пустым списком, в котором он создает исключение). Этот метод перемещает “головку” так, чтобы она указывала на 2-й элемент (если таковой имеется), и уменьшает размер на “1”. Кроме того, он возвращает удаленные данные. Временная сложность составляет O(1), так как обход списка не требуется.

3. снимите На

В качестве аргумента он принимает целочисленный индекс (скажем, k), и если индекс действителен, он удаляет элемент “k-й” из связанного списка и уменьшает размер на “1”.

Кроме того, он возвращает удаленные данные. В случае, если удаляемый элемент является “Первым” или “Последним”, он вызывает “удалить первым” или “Удалить последним” соответственно.

В этой операции мы также используем другую функцию “getNodeAt”, которая является закрытым членом класса Связанного списка. Эта функция принимает в качестве аргумента целочисленный индекс, и если индекс допустим (т. Е. Если и индекс <размер связанного списка), она возвращает узел с этим индексом.

Таким образом, в этой функции требуется обход списка, следовательно, он имеет значение O(n), что делает временную сложность операции “RemoveAt” равной O(n).

Реализация методов вставки и удаления связанного списка в Java

package com.journaldev.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();

	}

}

Выход

Реализация вставки и удаления связанного списка в Java