博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
链接列表插入删除方法
阅读量:2531 次
发布时间:2019-05-11

本文共 8395 字,大约阅读时间需要 27 分钟。

链接列表插入方法 (Linked List Insert Methods)

Addition In Linked List

Linked List Insert

链表插入

Linked List insert methods allow us to insert a Node at a specific place. There are three insert methods based on the position where the new node is inserted.

链接列表插入方法使我们可以在特定位置插入Node。 根据插入新节点的位置,有三种插入方法。

  1. addLast

    addLast
  2. addFirst

    addFirst
  3. addAt

    addAt

1. addLast (1. addLast)

As the name suggests, the new node is appended at the last position of the Linked list. The Linked List size is increased by 1. The “tail” points to the newly added Node. Since we have tail Node, the time complexity is O(1) else it would have been O(n).

顾名思义,新节点将附加在“链接”列表的最后一个位置。 链接列表的大小增加1。“ tail”指向新添加的Node。 由于我们有尾节点,因此时间复杂度为O(1),否则为O(n)。

2. addFirst (2. addFirst)

The new node is added at the first position of the Linked list. The Linked List size is increased by 1. The “head” points at the newly added Node. The time complexity is O(1) as there is no traversal of List is involved.

新节点将添加到“链接”列表的第一个位置。 链接列表的大小增加1。“ head”指向新添加的Node。 由于不涉及List的遍历,因此时间复杂度为O(1)。

3. addAt (3. addAt)

This method has two arguments – the Node to insert and an integer index (say ‘k’). The node is added at the kth position of the Linked list. The linked list size is increased by 1.

此方法有两个参数–要插入的Node和一个整数索引(例如'k')。 节点被添加到“链接”列表的第k个位置。 链接列表的大小增加1。

In case the element to be added is “First” or “Last” then it calls “addFirst” or “addLast” respectively.

如果要添加的元素是“ First”或“ Last”,则分别调用“ addFirst”或“ addLast”。

In this operation, we also use another function “getNodeAt” which is a private member of Our Linked List class. This function takes an integer index as an argument and if the index is valid (i.e. if index>=0 and index <size of the Linked list) it returns the Node at that index.

在此操作中,我们还使用另一个函数“ getNodeAt”,它是我们的链接列表类的私有成员。 该函数将整数索引作为参数,如果索引有效(即,如果索引> = 0,并且索引<链表的大小),则它将返回该索引处的节点。

Thus in this function traversal of the linked list is required. The time complexity of addAt() function is O(n).

因此,在此功能中,需要遍历链接列表。 addAt()函数的时间复杂度为O(n)。

链接列表删除方法 (Linked List Delete Methods)

Deletion In Linked List

Linked List Delete

链接列表删除

Linked List supports three methods to delete nodes.

链表支持三种删除节点的方法。

  1. removeLast

    removeLast
  2. removeFirst

    removeFirst
  3. removeAt

    removeAt

1.删​​除最后 (1. removeLast)

This method removes the last element of the Linked list (Provided the list is not an empty list, in which it throws an exception). It moves the “tail” to point towards the 2nd last element (if any ) and decreases the size by ‘1’. Also, it returns the removed data. Since we have tail Node, therefore, the time complexity is O(1) else it would have been O(n).

此方法删除链接列表的最后一个元素(提供的列表不是一个空列表,它会引发异常)。 它将“尾巴”移至最后一个第二个元素(如果有的话),并将大小减小“ 1”。 同样,它返回删除的数据。 由于我们有尾节点,因此,时间复杂度为O(1),否则为O(n)。

2. removeFirst (2. removeFirst)

It removes the first element of the Linked list (Provided the list is not an empty list, in which it throws an exception). This method moves the “head” to point towards the 2nd element (if any ) and decreases the size by ‘1’. Also, it returns the removed data. The time complexity is of O(1) as there is no traversal of List is involved.

它删除“链表”列表的第一个元素(如果列表不是空列表,则在其中引发异常)。 此方法将“ head”移至第二个元素(如果有的话),并将大小减小“ 1”。 同样,它返回删除的数据。 由于不涉及List的遍历,所以时间复杂度为O(1)。

3. removeAt (3. removeAt)

It takes an Integer index (let’s say k) as an argument and if the index is valid it removes the ‘kth’ element of the Linked list and decreases the size by ‘1’.

它使用一个整数索引(比如说k)作为参数,如果该索引有效,它将删除“链表”的“ kth”元素并将其大小减小“ 1”。

Also, it returns the removed data. In case the element to be removed is “First” or “Last” then it calls “removeFirst” or “removeLast” respectively.

同样,它返回删除的数据。 如果要删除的元素是“ First”或“ Last”,则分别调用“ removeFirst”或“ removeLast”。

In this operation, we also use another function “getNodeAt” which is a private member of the Linked List class. This function takes an integer index as an argument and if the index is valid (i.e. if index>=0 and index <size of the Linked list) it returns the Node at that index.

在此操作中,我们还使用另一个函数“ getNodeAt”,它是链接列表类的私有成员。 该函数将整数索引作为参数,如果索引有效(即,如果索引> = 0,并且索引<链表的大小),则它将返回该索引处的节点。

Thus in this function traversal of the list is required, therefore, it is of O(n) which makes the time complexity of operation “removeAt” to be O(n).

因此,在该函数中,需要遍历列表,因此,是O(n),这会使操作“ removeAt”的时间复杂度变为O(n)。

链表插入删除方法的Java实现 (Linked List Insert Delete Methods Implementation in 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();	}}

Output

输出量

Insertion Deletion In Java

Linked List Insert Delete Implementation in Java

Java中的链表插入删除实现

翻译自:

转载地址:http://uclzd.baihongyu.com/

你可能感兴趣的文章
Lunix文件的读写权限问题
查看>>
Liferay 7:portlet name
查看>>
PostgreSQL9.6.3的REDIS测试
查看>>
解决pycharm问题:module 'pip' has no attribute 'main'
查看>>
002 lambda表达式
查看>>
springboot添加自定义注解
查看>>
POJ 2391 Ombrophobic Bovines ( 经典最大流 && Floyd && 二分 && 拆点建图)
查看>>
JavaScript数组方法之reduce
查看>>
Linux常用命令之文件搜索命令
查看>>
thinkphp自定义权限管理之名称判断
查看>>
C++ ORM ODB 入门介绍(一)
查看>>
C#_02.14_基础五_.NET类
查看>>
Flask 学习资源
查看>>
Android SDK下载和更新失败的解决方法 分类: Android...
查看>>
MVC2 强类型的 HTML Helper
查看>>
开发 Windows 8 应用 - 0 - windows 8 开发资源
查看>>
生成二维码图片的工具类
查看>>
Surface Pro 4远程桌面分辨率问题
查看>>
【转】包管理器Bower详细讲解
查看>>
JS膏集02
查看>>