This is the 16th day of my participation in Gwen Challenge

Introduction to the

Linked lists are also linear data structures, but unlike arrays, the underlying storage units are discontinuous. The order of a linked list depends on Pointers. Structurally, a linked list node usually includes a data field and a pointer field. A singly linked list is one in which the pointer field has only one pointer that points to the nodes behind the node. The following is the classic definition of a singly linked list.

/ / c + + version
// Definition for singly-linked list.
struct SinglyListNode {
    int val;
    SinglyListNode *next;
    SinglyListNode(int x) : val(x), next(NULL) {}};Copy the code
/ / Java version
// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(intx) { val = x; }}Copy the code

Single linked list structure diagram:

Single linked list common operations

Add nodes in the middle of the list

  • 1. Initialize the new node with the given valuecur;

  • 2. Link cur next to next node of PREv.

  • 3. Link the next field in prev to cur.

Unlike arrays, we do not need to move all elements after the inserted element. Therefore, you can insert new nodes into the linked list in O(1) time complexity, which is very efficient. However, in practice, it is usually necessary to traverse the linked list to find the insertion location, and the time complexity of this search process is O(n).

Add nodes in the table header

  • Initialize a new nodecur
  • Link the new node to our original headerhead.
  • willcurSpecified ashead 。

Unlike adding a node in the middle, adding a node at the head of the table has no search process and the total time complexity is only the cost of inserting the node, hence O(1).

Remove nodes

  • Find prev and next (cur);

  • Next, link prev to cur’s next node, Next.

In our first step, we need to find prev and Next. It’s easy to find Next using cur’s reference field, but we have to traverse the list from scratch to find Prev, whose average time is O(N), where N is the length of the list. Therefore, the time complexity of deleting nodes will be O(N).

The space complexity is O(1), because we only need constant space to store Pointers.

Find nodes

The search node is generally divided into: search the node content of the specified location and search the node location of the specified element. Finding the node position of the specified element, needless to say, must be done by traversing the list, so the time is O(n) complex. Because the underlying storage of the linked list is not continuous, it cannot be searched by index. For the contents of nodes in a specified location, the linked list can only be searched through the table head one by one, and its time complexity is also O(n).

Design a linked list

Implement these functions in the linked list class:

  • Get (index) : Gets the value of the index node in the list. If the index is invalid, -1 is returned.
  • AddAtHead (val) : Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the linked list.
  • AddAtTail (val) : Appends a node with the value val to the last element of the list.
  • AddAtIndex (index,val) : Adds a node with the value val before the index node in the linked list. If index is equal to the length of the list, the node is appended to the end of the list. If index is greater than the list length, no node will be inserted. If index is less than 0, insert the node in the header.
  • DeleteAtIndex (index) : Deletes the index of the list if the index index is valid.
public class ListNode {
  int val;
  ListNode next;
  ListNode(intx) { val = x; }}class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  public MyLinkedList(a) {
    size = 0;
    head = new ListNode(0);
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    ListNode curr = head;
    // index steps needed 
    // to move from sentinel node to wanted index
    for(int i = 0; i < index + 1; ++i) curr = curr.next;
    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    addAtIndex(0, val);
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    addAtIndex(size, val);
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length, 
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative, 
    // the node will be inserted at the head of the list.
    if (index < 0) index = 0;

    ++size;
    // find predecessor of the node to be added
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // node to be added
    ListNode toAdd = new ListNode(val);
    // insertion itself
    toAdd.next = pred.next;
    pred.next = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    size--;
    // find predecessor of the node to be deleted
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // delete pred.next pred.next = pred.next.next; }}Copy the code