list-based collection

1. 콜렉션(Collection)은 어떤 것들의 집합이다.

 

2. 리스트(List)는 콜렉션의 확장이다. 리스트에는 순서가 있다. 언어의 종류에 따라서 리스트는 핵심 기능을 담당한다.

 

3. 리스트에는 순서가 있다. 

 

4. 배열(Array)는 인덱스가 있는 콜렉션이다. 인덱스는 일종의 태그다.  배열은 생성 될 때 그 사이즈가 결정된다. 배열에서도 배열에 변형을 가할 때, 주위 인덱스에 영향을 준다면, 변형하는 요소 외에도 큰 영향을 주게되어 자원이 많이 소모된다.

 

4-1. 예를 들면, 리스트에 어떤 요소를 삽입하는 것은 상수 배로 일어나기 때문에 쉽다. 하지만 어레이로 삽입하는 것은 O(n)의 시간이 소요된다. 왜냐하면 삽입하려는 하나의 요소로 인하여 다른 요소들을 움직여야 하거나, 공간이 모자라다면 새로운 배열 위에 모든 것을 복사해야 할 수도 있기 때문이다. 즉, 파이썬 리스트에 삽입하는 것은 O(n) 만큼이 소요되는 반면, 특정 지점의 어떤 원소를 찾는 수행은 O(1)이다. 

 

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Pop last	O(1)	O(1)
Pop intermediate	O(k)	O(k)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)

 

 

5. linked list와 array는 많이 다르다.

 

구글 이미지

5-1. 링크드 리스트는 리스트의 확장판이지, 배열과는 전혀 연관이 없다. 여전히 순서는 있지만 인덱스는 존재하지 않는다. 즉, 리스트는 상호의 연결로서 특징화 된다. 리스트는 양 옆에는 어떤 원소가 있다는 개념은 있지만, 이 리스트가 얼마나 긴지, 어디에 위치하는지에 대한 정보는 없다. 

 

5-2. 하지만 배열은 다르다. 어떤 어레이도 옆에 있는 배열에 대한 정보를 가지고 있지 않다. 오로지 인덱스(색인)에 의해서만 알 수 있다. 다음 배열을 알기 위해서는 다음 배열의 인덱스가 필요하다.

 

5-3. 이런 차이점이 발견되고, 배열이 사용되는 이유는 위에서 언급한 것과 같이 비용문제이다. 데이터에 변형을 가할 때, 이 작업은 정말 복잡하기 때문이다. 하지만 배열을 사용한다면, 인덱스만 알기만 한다면 그냥 빼고 넣을 수 있다. 아주 쉽게.

 

6. 링크드 리스트에서 각 요소는 할당된 값 뿐만 아니라, 메모리에서의 위치 값과, 다음 리스트 요소의 위치 값을 가지고 있다. Doubly리스트의 경우 이전과 다음 요소의 위치 값을 가지고 있기 때문에 검색을 좌우로 횡단할 수 있게 된다.

 

6-2.그렇기 때문에 리스트의 요소가 변경될 때, 할당된 위치 값은 최악의 경우, 리스트의 요소만큼 변경되어야 한다.''

 

 

\

insert, delete, 위치찾기 모두 링크드 리스트에서는 모든 원소의 위치 값을 변경시켜 주어야 한다는 것은 알겠지만

구체적으로 이 값이 작동하는 방식에 대해서는 아직 이해가 잘 가진 않는다.

 

손으로 쓰면서 하니까 이해가 간다. 링크드 리스트가 무엇을 바탕으로 원소에 접근하는지에 대해서 기억해야 한다.

링크드 리스트는 양 옆의 원소에 의지해서 위치 값을 가진다. 그렇기 때문에 반복문이 판별해야 하는 것은

지금 무슨 값인가? 하는 current다. 그리고 그 다음 값은 무엇이냐는 current.next다.

 

그렇기 때문에 기준이 되는 첫째 원소는 head라는 태그를 가지게 되는 것이다.

그렇기 떄문에 마지막 원소는 tail이라는 별명을 가지게 되어서 current.next값이 none이게 된다.

 

 

"""The LinkedList code from before is provided below.
Add three functions to the LinkedList.

"get_position" returns the element at a certain position.

The "insert" function will add an element to a particular
spot in the list.

"delete" will delete the first element with that
particular value.

Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""



class Element(object): # 클래스 Element 선언
    def __init__(self, value): # 클래스 Element의 초기화자 설정 argument로 value를 명시
        self.value = value # value는 값 자체가 value다.
        self.next = None # Element로 선언된 객체 내의 next라는 변수에 None을 할당
        
class LinkedList(object): # LinkedList라는 클래스 선언
    def __init__(self, head=None): # LinkedList의 초기화자 설정, argument head의 기본 값은 None
        self.head = head # 변수 head의 값은 head임.
        
    def append(self, new_element): # append 함수 선언, new_element를 argument로 받음
        current = self.head # 변수 current 에 인스턴스의 head값 할당 
        if self.head: # head 값이 존재 할 시
            while current.next: # current의 next 값이 존재 할 시, while 반복문을 시행
                current = current.next # 현재 current.next 값을 current에 할당, 다시 while 반복문 실행
            current.next = new_element # current.next 값이 None 값일 때까지 실행한 후, while반복문에서 나와 new element를 current.next에 할당
            
        else: #self.head의 값이 존재 하지 않는다면 
            self.head = new_element # 인스턴스의 head에 new_element를 할당
    

 

---이어서
	def get_position(self, position): #Linkedlist 내의 get_position 함수 선언, argument로는 postion을 받아옴
        counter = 1 # 지역 변수 counter에 1을 할당하고
        current = self.head # 지역 변수 current에 Linkedlist의 head값 할당
        if position < 1: # 찾으려는 position이 1보다 작다면
            return None # None 값을 반환
        while current and counter <= position: # current 값이 존재하고, counter의 값이 position 보다 작거나 같다면 반복문 수행
            if counter == position: # if counter와 position이 일치한다면
                return current # current의 값을 반환
            current = current.next # 일치하지 않는다면, current.next 값을 current에 할당
            counter += 1 # counter + 1
        return None #while문 종료시 반환 값은 없음.

 

 

 

 

 

 

 

7. 스택(Stack)은 list_based structure다. 다른 것 필요 없고, 현실 세계의 팬케잌이 쌓여 있는 것과 똑같다. 그렇기 때문에 맨 위에 있는 자료에 접근하기 가장 쉽다.

 

7-1. 스택에 넣을 때 Push, 뺄 때를 Pop이라고 한다. 둘 모두 빅오 표기법으로 O(1)이다.

 

7-2. LIFO : LAST IN FIRST OUT : 나중에 들어간 놈이 먼저 나온다가 스택의 정신이다.

 

 

8. Queues. FIFO :FIRST IN FIRST OUT, 큐의 정신이다.

 

8-1.가장 오래된 것, 가장 처음의 것을 해드, 디큐, 픽이라고 부른다.

8-2.새로운 것, 가장 마지막의 것을 테일, 엔큐라고 부른다.

8-3. priority 큐라는 것이 있는데, 우선 순위에 따라서 먼저 나가며, 우선순위가 동일할 때는 먼저 들어온 것이 먼저 나간다.

 

 

9. 덱이라고 부르는 양방향 큐는 큐로도 되며, 스택도 될 수 있다.