链表Linked List-插入 En（1）

绝地灬酷狼 2023-09-24 18:35 126阅读 0赞

# 1.What is Linked List？ #

*  Like arrays, **a Linked List is `a linear data structure`.**
 *  Unlike arrays, linked list elements are **not stored at a contiguous location**; **the elements are linked `using pointers`**.
 *  They include a series of connected nodes. Here, **each node stores the data and the address of the next node**.  
    ![在这里插入图片描述][c83e2460103147059e8fb5c24c40154b.png]

# 2. Why Linked List? #

> Arrays can be used to **store linear data of similar types**, but arrays have the following limitations:

*  The size of the arrays is **fixed**:
    
     *  So we must know the **upper limit on the number of elements** in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
 *  **Insertion of a new element / Deletion of a existing element** in an array of elements is expensive:
    
     *  The room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

## 1).Advantages of Linked Lists over arrays ##

*  `Dynamic Array`.
 *  `Ease of Insertion/Deletion`.

## 2) Drawbacks of Linked Lists: ##

*  **Random access is not allowed**. We have to **access elements sequentially starting from the first node(head node)**. So we cannot do a binary search with linked lists efficiently with its default implementation.
 *  **`Extra memory space for a pointer` is required with each element of the list.**
 *  `Not cache-friendly`. Since array elements are contiguous locations, there is the locality of reference which is not there in the case of linked lists.
 *  **It takes a lot of time in traversing and changing the pointers**.
 *  **Reverse traversing is not possible** in `singly linked lists`.
 *  It will be confusing when we work with pointers.
 *  Direct access to an element is not possible in a linked list as in an array by index.
 *  `Searching for an element` is costly and requires `O(n) time`complexity.
 *  Sorting of linked lists is very complex and costly.

## 3)Types of Linked Lists ##

*  `Simple Linked List` – In this type of linked list, one can move or traverse the linked list in`only one direction`. where **the next pointer of each node points to other nodes but the next pointer of the `last node points to NULL`.** It is also called “Singly Linked List”.
 *  `Doubly Linked List` – In this type of linked list, one can move or traverse the linked list in both directions (**`Forward and Backward`**)
 *  `Circular Linked List` – In this type of linked list, **the last node of the linked list contains the link of the first/head node of the linked list in its next pointer.**
 *  `Doubly Circular Linked List` – `A Doubly Circular linked list`or `a circular two-way linked lis`t is **a more complex type of linked list** that contains a pointer to the next as well as the previous node in the sequence. The circular doubly linked list does not contain null in the previous field of the first node.
 *  `Header Linked List` – A header linked list is **a special type of linked list** that contains ***a header node at the beginning of the list***.

## 4)Basic operations on Linked Lists ##

*  Deletion
 *  Insertion
 *  Search
 *  Display

## 5)Representation of Singly Linked Lists ##

*  `A linked list` is represented by *a pointer to the first node of the linked list.*
 *  `The first node` is called the `head` of the linked list.
 *  If the linked list is empty, then the value of the head points to `NULL`.
 *  Each node in a list consists of at least two parts:
    
     *  **A Data Item** (we can store integers, strings, or any type of data).
     *  **Pointer** (Or Reference) to the next node (connects one node to another) or `An address of another node`

class LinkedList {
        
    	Node head; // head of the list
    
    	/* Linked list Node*/
    	class Node {
        
    		int data;
    		Node next;
    
    		// Constructor to create a new node
    		// Next is by default initialized
    		// as null
    		Node(int d)
    		{
        
    			data = d;
    			next = null;
    		}
    	}
    }

# 3.Traversal of a Linked List #

public class LinkList {
        
        Node head; // head of list
    
        /* Linked list Node*/
        static class Node {
        
            int data;
            Node next;
            Node(int d)
            {
        
                data = d;
                next = null;
            }
        }
        public void printList(){
        //此函数打印链表的内容开始 从头部
            Node n = head;
            while(n!=null){
        
                System.out.print(n.data);
                n=n.next;
            }
        }
    
        public static void main(String args[])
        {
        
            LinkList list = new LinkList();/* Start with the empty list. */
            list.head= new Node(1);
            Node second = new Node(2);
            Node third = new Node(3);
    
            list.head.next= second;// Link first node with the second node
            second.next= third;//Link second node with the third node
            list.printList();
    
        }
    }

## Time Complexity: ##

<table> 
 <thead> 
  <tr> 
   <th>Time Complexity</th> 
   <th>Worst Case</th> 
   <th>Average Case</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Search</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>Insertion</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>Deletion</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

*  `Search` is`O(n)` because as data is **not stored in contiguous memory locations so we have to traverse one by one**.
 *  `Insertion and Deletion` are `O(1)` because we have to just **link new nodes for Insertion with the previous and next node** and dislink exist nodes for **deletion from the previous and next nodes** without any traversal.

# 4. Insertion in Linked List #

A node can be added in`three ways`

*  At the front of the linked list
 *  After a given node.
 *  At the end of the linked list.

> ## 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 data  
> 3. Make next of new Node as head  
> 4.Move the head to point to new Node

### Code ###

/* This function is in LinkedList class. Inserts a
    new Node at front of the list. This method is
    defined inside LinkedList class shown above */
    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;
    }

### 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.
 *  Then, allocate a new node and
 *  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 ###

/* This function is in LinkedList class.
    Inserts a new node after the given prev_node. This method is
    defined inside LinkedList class shown above */
    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. Allocate the Node &
    	3. 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;
    }

### 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
> 5.  Else traverse till the last node
> 6.  Change the next of last node

### Code ###

/* 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;
    		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;
    }

### 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)`

### Uses all of the above methods to create a linked list. ###

// 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

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

### An alternate method by using a constructor call: ###

// Alternate method to declare the class
    // in order to minimize the
    // memory allocation work
    
    import java.io.*;
    
    class node {
        
    	int data;
    	node next;
    
    	// constructor call
    	node(int value)
    	{
        
    
    		// It automatically assigns the value to the data
    		data = value;
    
    		// next pointer is pointed to null
    		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();
    	}
    }
    
    // This code is contributed by lokeshmvs21.

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

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

[c83e2460103147059e8fb5c24c40154b.png]: https://img-blog.csdnimg.cn/c83e2460103147059e8fb5c24c40154b.png
[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