Array vs Linked List

Array:

• An array has a fixed data space. To increase the space, a new array must be built with the specified length.
• To index an array (Such as array[0]), it takes O(1).
• To add an element in the middle of an array, the element must be appended, then the pointer is moved element by element to the desired place. This takes O(N).
  

Linked list:

• Every element is linked to the next element, such as [1] -> [2] -> [3] etc. where [1] is a node and -> is a pointer
• To index a linked list, it takes O(N), as the index moves node by node from the first node to the Nth node.
• To add a node in the middle of a linked list, the pointer is changed to the new node to be added in between.

Inserting and deleting with Linked List
https://devopedia.org/linked-list-data-structure

	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

What does Python use?

• Python's list is an array.
• However, it uses a dynamic array, so that append() or extending the length of the list take O(1)

Class

• The constructor is the function used to create a class
  - For example, if there is a class Person, then Person() is the constructor
  • To create settings for the constructor, create the def __init__(self): function in the class definition, meaning __init__ will run when a new class is made

Creating the LinkedList class

A Linked List is composed a Node, Pointer (next), and a head (the first node)

• The class Node has 1. data and 2. a pointer (next)
• The class Linked List has the head Node
  - The next to the end of a Linked List is None [1] -> [2] -> [3] -> None
  • To append() to the linked list, the head must move through each Node until the next value is None
  • When the head is None, there is no next value None. In this case, an error should occur, so just add the data to the current head.