(3) List

List는 순서가 있는 자료형입니다. (1) 배열과 (2) 링크드리스트가 있습니다.

1. Array (배열)

(1) Static / Dynamic Array

파이썬에서 구현된 list는 array를 통해 구현한 array list를 말합니다.

추가적으로 말하면, c언어상에서 array를 통해서 dynamic array를 구현하는데, dynamic array를 통해 구현한 list가 파이썬에서 구현한 list입니다.

그래서 파이썬에서 list는 고정된 길이를 가지고 있지 않죠!

(2) Array의 시간복잡도

링크드리스트와 비교하여 공부해야하는 부분입니다!

내부적으로, 더 들어가면 dynamic array는 기본 array가 꽉 차면 double로 resizing 해주는 방식인데, resizing 하고 이 전에 array를 다시 적어줘야 하기 때문에 resizing 마다 O(n) 가 소요됩니다. 하지만, 분할상환 기법을 통해서 amortized O(1) 입니다.

다시 본론으로 오면, 배열은 access가 많고, 중간에 insert와 delete는 적은 경우 사용하면 좋은 자료구조입니다. 이유는? 배열의 random_access 특징 때문입니다!

(3) Array 사용하는 경우

1. 반복문
2. Sort & Two Pointer (보통, 포인터는 sort 된 자료형에 사용)

🍓 twoSum 문제

# 문제 상황 : 입력배열의 2개의 숫자를 더해서 target값이 될 수 있는 경우가 있다면 False 출력  
# 오류 파악 : 중복하면 안된다. 
# 입력제한 : 0 < len(nums) <= 10^4
# 시간복잡도 : O(nlogn)

# Sort & Two Pointer 로 접근!

def twoSum(nums, target):
    nums.sort()
    start, end = 0, len(nums)-1
    while start != end:
        if nums[start]+ nums[end] > target:
            end -= 1
        elif nums[start]+ nums[end] < target:
            start += 1
        elif nums[start]+ nums[end] == target:
            return True
    return False

---

2. LinkedList (링크드리스트)

(1) 노드와 링크드리스트

Node라는 구조체가 연결되는 구조가, linkedList 입니다.

Node에 value 와 next_node의 주소값 이 들어있는게 기본 형태입니다.

Node에 valuem, next_node의 주소값과 prev_node의 주소값이 들어있는 양방향 노드로 연결된 링크드리스트를, doubly linkedLisk 라고 합니다.

(2) 링크드리스트 구현하기

[설명그림 및 코드 접기/펼치기]

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

class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None            # appendTail()
    
    def append(self, value):        # BigO(n)
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            cur = self.head
            while (cur.next) :
                cur = cur.next
            cur.next = new_node
    
    def appendTail(self, value):    # BigO(1)
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        

    def insert(self, idx, value):
        new_node = Node(value)
        cur = self.head
        if idx == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            for _ in range(idx-1):
                cur = cur.next
            new_node.next = cur.next
            cur.next = new_node     
    
    def get(self, idx):
        cur = self.head
        for _ in range(idx):
            cur = cur.next
        return cur.value

    def remove(self,idx):
        if idx == 0:
            self.head = self.head.next
        else:
            prev = self.head
            for _ in range(idx-1):
                prev = prev.next
            prev.next = prev.next.next  # garbage collecter가 참조없는 거 삭제

    def printAll(self):
        current = self.head
        while(current):
            print(current.value)
            current = current.next
        print('----------------')


li = LinkedList()
li.appendTail(1)
li.appendTail(2)
li.appendTail(3)
# li.insert(100,0)
li.printAll()
li.remove(0)
li.remove(1)
li.printAll()

(3) 링크드리스트 시간복잡도

Array와 비교해보면, linkedList는 맨 앞이나 맨 뒤에 추가 및 삭제가 많을 때 용이합니다.

(4) 링크드리스트 사용하는 경우

1. 선형 자료구조 + 중간에 데이터 추가 및 삭제 시
2. Tree or Graph에 활용

🍓 Browser-History 문제

# Doubly linkedList 로 풀기
# 시간 복잡도 : O(4900*100) (back O(n), forward O(n))

class Node(object):
    def __init__(self, url=0, prev=None, next=None):
        self.url = url
        self.prev = prev
        self.next = next

class BrowserHistory(object):
    def __init__(self, homepage):
        self.head = self.cur = Node(homepage)   # 여기서, head는 형식상 포인터
    
    def visit(self, url):
        new_node = Node(url=url, prev=self.cur)
        self.cur.next = new_node
        self.cur = new_node
        
    def back(self, steps):
        while steps>0 and self.cur.prev is not None:
            steps -= 1
            self.cur = self.cur.prev
        return self.cur.url         
        
    def forward(self, steps):
        while steps > 0 and self.cur.next is not None:
            steps -= 1
            self.cur = self.cur.next
        return self.cur.url

[List로 푸는 경우, 코드 접기/펼치기]

# list로 풀어도 복잡도는 같음
# 시간 복잡도 : O(4900*100) (visit O(n))

class BrowserHistory(object):
    def __init__(self, homepage):
        self.lt = [homepage]
        self.cur = 0                # idx

    def visit(self, url):
        while self.cur != len(self.lt)-1:
            self.lt.pop()
        self.lt.append(url)
        self.cur += 1
    
    def back(self, steps):
        if steps > self.cur:
            self.cur = 0
        else:
            self.cur -= steps
        return self.lt[self.cur]
    
    def forward(self, steps):
        if steps > len(self.lt)- self.cur -1:
            self.cur = len(self.lt) -1
        else:
            self.cur += steps
        return self.lt[self.cur]

🍓 이외의 leetcode 문제

https://leetcode.com/problems/reverse-string/

https://leetcode.com/problems/delete-node-in-a-linked-list/

결론적으로, 순서가 있는 자료형에서 접근이 많은 경우는 배열을 사용하고, 순서가 있는 자료형에서 맨 앞이나 맨 뒤에 insert나 delete가 많은 경우는 링크드리스트를 사용합니다.

다음에는 스택에 대해서 포스팅 하겠습니다 :)

해당 시리즈의 포스트는 인프런에서 제공하는 개발남노씨의 코딩테스트 강의 를 바탕으로 작성하였습니다.