链表Linked List-插入的3种方法（9）

野性酷女 2023-09-24 20:23 44阅读 0赞

# 1. 链表插入Insertion in Linked List #

可以通过`三种方式`添加节点

*  At the front of the linked list 在链表的前面
 *  After a given node. 在给定节点之后。
 *  At the end of the linked list.在链接列表的末尾。

# 2.解决方法 #

> ## 1)在链表的前面Add a node `at the front`: (4 steps process) ##

### Approach: ###

*  The new node is always added `before the head` of the given Linked List.
 *  And `newly added node becomes the new head` of the Linked List.
 *  For example, if the given Linked List is `10->15->20->25` and we add an item 5 at the front, then the Linked List becomes `5->10->15->20->25`.
 *  Let us **call the function that adds at the front of the list is `push()`.** The push() must **receive a pointer to the head pointer** because ***the push must change the head pointer to point to the new node***

![在这里插入图片描述][bf665af33c3949859ede694cf5d0797f.png]

> 1 & 2: Allocate the Node &Put in the data1&2：分配节点&放入数据  
> 3. Make next of new Node as head将新节点的下一个作为头部  
> 4.Move the head to point to new Node移动头部指向新节点

### Code ###

public void push(int new_data)
    {
        
    	Node new_node = new Node(new_data);//分配节点&放入数据
    	new_node.next = head;//将新节点的下一个作为头部
    	head = new_node;//移动头部指向新节点
    }

### Complexity Analysis: ###

`Time Complexity`: `O(1)`, We have a pointer to the head and we can directly attach a node and change the pointer. So the Time complexity of inserting a node at the head position is O(1) as it does a constant amount of work.  
`Auxiliary Space`: `O(1)`

> ## 2)在给定节点之后添加一个节点Add a node `after a given node`: (5 steps process) ##

### Approach: ###

We are given a pointer to a node, and the **new node is inserted after the given node.**

Follow the steps to add a node after a given node:

*  Firstly, check if the given previous node is NULL or not.首先，检查给定的前一个节点是否为 NULL。
 *  Then, allocate a new node 然后，分配一个新节点
 *  Assign the data to the new node将数据分配给新节点
 *  And then make the next of new node as the next of previous node. 然后将新节点的下一个作为前一个节点的下一个。
 *  Finally, move the next of the previous node as a new node.最后，移动前一个节点的下一个作为新节点。  
    ![在这里插入图片描述][308e9d71116a44d7acf2a2b8b69db0b9.png]

### Code ###

public void insertAfter(Node prev_node, int new_data)
    {
        
    	/* 1. 检查给定的节点是否为空 */
    	if (prev_node == null) {
        
    		System.out.println(
    			"The given previous node cannot be null");
    		return;
    	}
    
    	/* 2. 分配节点 & 3.放入数据*/
    	Node new_node = new Node(new_data);
    
    	/* 4.将新节点的下一个作为 prev_node 的下一个 */
    	new_node.next = prev_node.next;
    
    	/* 5. 将 prev_node 的下一个作为 new_node*/
    	prev_node.next = new_node;
    }

### Complexity Analysis: ###

`Time complexity`: `O(1)`, since prev\_node is already given as argument in a method, no need to iterate over list to find prev\_node  
`Auxiliary Space`: `O(1)` since using constant space to modify pointers

> ## 3)在“末尾”添加一个节点 Add a node `at the end`: (6 steps process) ##

*  The new node is always added **after the last node of the given Linked List.**
 *  For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
 *  Since a Linked List is typically represented by the head of it, we have to traverse the list till the end and then change **the next to last node to a new node.**  
    ![在这里插入图片描述][327a93320b0343a2aace8bc7baaa3ee8.png]

### Approach: ###

> 1.  Allocate the Node &分配节点
> 2.  Put in the data放入数据
> 3.  Set next as null将下一个设置为空
> 4.  1)If the Linked List is empty, then make the new node as head如果链表为空，则将新节点作为头节点  
>     2)This new node is going to be the last node, so make next of it as null 这个新节点将成为最后一个节点，所以将它的下一个设为 null
> 5.  Else traverse till the last node否则遍历到最后一个节点
> 6.  Change the next of last node更改最后一个节点的下一个

### Code ###

public void append(int new_data)
    {
        
    	/* 1.分配节点 2.放入数据3. 将下一个设置为空*/
    	Node new_node = new Node(new_data);
    	/* 4. 如果链接列表为空，则使 新节点作为头 */
    	if (head == null)
    	{
        
    		head = new_node;
    		return;
    	}
    	/* 4. 这个新节点将成为最后一个节点，所以 将它的下一个设为空 */
    	new_node.next = null;
    	/* 5. 否则遍历到最后一个节点 */
    	Node last = head;
    	while (last.next != null)
    		last = last.next;
    	/* 6. 更改最后一个节点的下一个 */
    	last.next = new_node;
    	return;
    }

### Complexity Analysis: ###

`Time complexity`: `O(N)`, where N is the number of nodes in the linked list. Since there is **a loop from head to end**, the function does O(n) work.  
This method can also be optimized to work in O(1) by keeping an extra pointer to the tail of the linked list  
`Auxiliary Space`: `O(1)`

# 3.使用上述所有方法创建链表 #

`Time Complexity`: `O(N)`  
`Auxiliary Space`: `O(1)`

// A complete working Java program to demonstrate all insertion methods
    // on linked list
    import java.io.*;
    public class LinkedList
    {
        
    	Node head; // head of list
    
    	/* Linked list Node*/
    	class Node
    	{
        
    		int data;
    		Node next;
    		Node(int d) {
        data = d; next = null; }
    	}
    
    	/* Inserts a new Node at front of the list. */
    	public void push(int new_data)
    	{
        
    		/* 1 & 2: Allocate the Node &
    				Put in the data*/
    		Node new_node = new Node(new_data);
    
    		/* 3. Make next of new Node as head */
    		new_node.next = head;
    
    		/* 4. Move the head to point to new Node */
    		head = new_node;
    	}
    
    	/* Inserts a new node after the given prev_node. */
    	public void insertAfter(Node prev_node, int new_data)
    	{
        
    		/* 1. Check if the given Node is null */
    		if (prev_node == null)
    		{
        
    			System.out.println("The given previous node cannot be null");
    			return;
    		}
    
    		/* 2 & 3: Allocate the Node &
    				Put in the data*/
    		Node new_node = new Node(new_data);
    
    		/* 4. Make next of new Node as next of prev_node */
    		new_node.next = prev_node.next;
    
    		/* 5. make next of prev_node as new_node */
    		prev_node.next = new_node;
    	}
    	
    	/* Appends a new node at the end. This method is
    	defined inside LinkedList class shown above */
    	public void append(int new_data)
    	{
        
    		/* 1. Allocate the Node &
    		2. Put in the data
    		3. Set next as null */
    		Node new_node = new Node(new_data);
    
    		/* 4. If the Linked List is empty, then make the
    			new node as head */
    		if (head == null)
    		{
        
    			head = new Node(new_data);
    			return;
    		}
    
    		/* 4. This new node is going to be the last node, so
    			make next of it as null */
    		new_node.next = null;
    
    		/* 5. Else traverse till the last node */
    		Node last = head;
    		while (last.next != null)
    			last = last.next;
    
    		/* 6. Change the next of last node */
    		last.next = new_node;
    		return;
    	}
    
    	/* This function prints contents of linked list starting from
    		the given node */
    	public void printList()
    	{
        
    		Node tnode = head;
    		while (tnode != null)
    		{
        
    			System.out.print(tnode.data+" ");
    			tnode = tnode.next;
    		}
    	}
    
    	/* Driver program to test above functions. Ideally this function
    	should be in a separate user class. It is kept here to keep
    	code compact */
    	public static void main(String[] args)
    	{
        
    		/* Start with the empty list */
    		LinkedList llist = new LinkedList();
    
    		// Insert 6. So linked list becomes 6->NUllist
    		llist.append(6);
    
    		// Insert 7 at the beginning. So linked list becomes
    		// 7->6->NUllist
    		llist.push(7);
    
    		// Insert 1 at the beginning. So linked list becomes
    		// 1->7->6->NUllist
    		llist.push(1);
    
    		// Insert 4 at the end. So linked list becomes
    		// 1->7->6->4->NUllist
    		llist.append(4);
    
    		// Insert 8, after 7. So linked list becomes
    		// 1->7->8->6->4->NUllist
    		llist.insertAfter(llist.head.next, 8);
    
    		System.out.println("\nCreated Linked list is: ");
    		llist.printList();
    	}
    }
    // This code is contributed by Rajat Mishra

Created Linked list is:  1 7 8 6 4

# 4. 使用构造函数调用的替代方法 #

`Time Complexity`: `O(N)`  
`Auxiliary Space`: `O(1)`

import java.io.*;
    
    class node {
        
    	int data;
    	node next;
    	node(int value)	{
        
    		data = value;
    		next = null;
    	}
    }
    
    class GFG {
        
    	// Declaring an empty linked list
    	static node head = null;
    	// Function to insert an element at head position
    	static void insertathead(int val){
        
    		node n = new node(val);
    		n.next = head;
    		head = n;
    	}
    	// Function to insert a element at a specified position
    	static void insertafter(int key, int val)
    	{
        
    		node n = new node(val);
    		if (key == head.data) {
        
    			n.next = head.next;
    			head.next = n;
    			return;
    		}
    		node temp = head;
    		while (temp.data != key) {
        
    			temp = temp.next;
    			if (temp == null) {
        
    				return;
    			}
    		}
    		n.next = temp.next;
    		temp.next = n;
    	}
    
    	// Function to insert an element at the end
    	static void insertattail(int val)
    	{
        
    		node n = new node(val);
    		if (head == null) {
        
    			head = n;
    			return;
    		}
    		node temp = head;
    		while (temp.next != null) {
        
    			temp = temp.next;
    		}
    		temp.next = n;
    	}
    
    	// Function to print the singly linked list
    	static void print()
    	{
        
    		node temp = head;
    		while (temp != null) {
        
    			System.out.print(temp.data + " -> ");
    			temp = temp.next;
    		}
    		System.out.println("NULL");
    	}
    
    	public static void main(String[] args)
    	{
        
    
    		insertathead(1);
    		insertathead(2);
    		System.out.print("After insertion at head: ");
    		print();
    		System.out.println();
    
    		insertattail(4);
    		insertattail(5);
    		System.out.print("After insertion at tail: ");
    		print();
    		System.out.println();
    
    		insertafter(1, 2);
    		insertafter(5, 6);
    		System.out.print(
    			"After insertion at a given position: ");
    		print();
    		System.out.println();
    	}
    }

After insertion at head: 2 -> 1 -> NULL
    
    After insertion at tail: 2 -> 1 -> 4 -> 5 -> NULL
    
    After insertion at a given position: 2 -> 1 -> 2 -> 4 -> 5 -> 6 -> NULL

[bf665af33c3949859ede694cf5d0797f.png]: https://img-blog.csdnimg.cn/bf665af33c3949859ede694cf5d0797f.png
[308e9d71116a44d7acf2a2b8b69db0b9.png]: https://img-blog.csdnimg.cn/308e9d71116a44d7acf2a2b8b69db0b9.png
[327a93320b0343a2aace8bc7baaa3ee8.png]: https://img-blog.csdnimg.cn/327a93320b0343a2aace8bc7baaa3ee8.png