Linked List

• In memory, an array is continuous while the linked list may not.

• Primitive Type is the type you already known4

• the length in the memory. Thus , String and ArrayList in Java are not primitive type.

• String a+"d" is O(N),** StringBuilder sb.append("d") is O(1).** The main reason is add function in String is actually find a new place of memory of length of a+ "d" and then copy the origin content in a and then copy the value of d.

• Useful algorithms about LinkedList:

• • Reverse

  • Delete

  • Traverse.

    ​

• Difference between LinkedList and ArrayList, The object in ArrayList can be anything while the element in LinkedList should be Node of anything.

• what's the difference between using tail pointer and without it???

  Answer:

• If you are only given one node in the linkedlist, and you are asked to delete that node, the only way is to:

  node.val = node.next.val;
  node.next = node.next.next;
  
  //copy the next to such node and then delete the next one.