코딩테스트

1. Sort & Two Pointer

O(nlogn) → 정렬을 할때의 시간복잡도.

two pointer → ex. [1,3,5,7,2] 여기서 두개의 포인터를 가지고 문제를 해결하는 방법. 거의 정렬이 된 상태에서 쓰임

.sort() —> 정렬함수

1. Linked list

Linked list 는 node로 구성.

Linked list는 node라는 구조체가 연결되는 형식.

node → 데이터 값과 next node의 주소값을 저장.

node → {value: next data}

linkedlist는 메모리상에서는 비연속적으로 저장되어있지만,

각각의 node가 next node의 메모리 주소값을 가리킴 → 논리적인 연속성.

물리적 비연속적, 논리적 연속적

각 node들은 데이터 저장 & next node의 address정보도 가짐.

—> 논리적 연속성 유지하며 연결 가능.

Array의 경우 → 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식 사용.

Linked list의 경우 → 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭다.

but, next node의 address도 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커짐.

<Node 구현>

class Node:
	def __init__(self, value = 0, next = None):
		self.value = value
		self.next = next

first = Node(1)
second = Node(2)
third = Node(3)
first.next = second
second.next = third
first.value = 6

insert_back() ( append() 구현 )

class LinkedList(object):
	def __init__(self):
		self.head = None
	def append(self, value):
		new_node = Node(value)
		if self.head is None:
			self.head = new_node
		# 맨 뒤의 node가 new_node를 가리켜야 한다.
		else:
			current = self.head
			while(current.next):
				current = current.next
			current.next = new_node

Linked list Operations

• get()
• insert_back()
• insert_front()
• insert_at(idx, value) → 링크드 리스트 중간인덱스에 노드를 추가하는 것
• remove_back()
• remove_front()
• remove_at(idx) → 중간의 node를 제거(제거하려는 노드 앞에가서, 주소값을 제거하려는 노드 뒤로 대체해준다.

insert_back (tail version O(1))