오늘 주제는 List 입니다!
배열과 결이 비슷한 주제로, 개발자분들이 가장 많이 사용하고 있지 않을까 하는 자료구조 중 하나입니다.
리스트는 배열의 개념과 헷갈릴 수 있기 때문에 분명하게 기억하시면서 혹은 직접 코드를 작성하시면서 따라오시면 좋을 것 같습니다. (저도 공부하다가 잠시 헤맸습니다😅)
그럼 시작해보겠습니다.
1. 개념
List는 배열과 마찬가지로 여러 데이터를 묶어서 저장하는 자료구조입니다.
저희는 평소에도 To-Do List나 장보기 리스트처럼 여러 데이터를 리스트 형태로 묶어서 관리하고 있습니다.
리스트의 가장 큰 특성은 아래와 같습니다. 배열과의 차이점으로 이해하셔도 좋을 것 같습니다.
- 리스트의 크기가 동적이다
- 여러 타입의 데이터를 저장할 수 있습니다
- 특정 값이 들어있는 공간의 삭제가 가능하다 (일반적인 배열의 경우 값이 없을 수는 있지만, 자리를 삭제하는 것은 불가합니다)
구현하는 방식에 따라 선형리스트, 연결리스트 두가지로 나누어지기 때문에 각각에 대해 설명하겠습니다.
1-1. 선형 리스트
선형리스트는 ArrayList 라고도 불리며, 배열을 기반으로 만들어진 리스트 형태입니다.
따라서 배열처럼 메모리 공간을 연속적으로 사용하기 때문에 논리적, 물리적 순서가 동일합니다. 또한 인덱스를 통해 값에 접근할 수 있습니다.
여기까지 공부하다보면 머리속에서 어? 그럼 배열이랑 다른게 뭐지? 라는 의문이 생깁니다.
선형리스트와 배열의 차이는 무엇일까요?
선형리스트와 배열의 가장 큰 차이는 크기 확장과 데이터의 삽입과 삭제에 있습니다.
배열은 데이터 삽입 시 기존의 데이터를 덮어쓰고, 삭제 시에는 값을 가지지 않게 됩니다. 즉, 공간은 항상 남아있는 것이죠
하지만 선형리스트는 데이터를 삽입하는 경우 뒤의 데이터를 한 칸씩 오른쪽으로 옮기게 됩니다. 마찬가지로 삭제시에는 공간 자체를 없애 왼쪽으로 모든 데이터를 한 칸씩 옮깁니다.
정리해보자면,
-
선형리스트는 빈자리 없이 데이터들이 저장되는 반면, 배열은 값이 없는 빈자리가 있을 수 있습니다.
-
배열은 크기가 정해져 있기 때문에 값을 추가한들 크기는 변하지 않습니다. 반면 선형리스트는 계속 값을 추가하는 경우 크기가 변하게 됩니다.
잘 이해가 되셨나요?
해당 부분을 제외하고는 배열과 거의 유사하다고 해도 무방합니다.
1-2. 연결 리스트
연결 리스트는 Linked List라고 불리며, 메모리의 동적 할당을 기반으로 구현된 리스트입니다.
연결리스트는 노드라는 개념이 있습니다.
노드는 포인터와 데이터를 가지고 있고, 이때 포인터는 다음 노드의 주소를 가리키고 있습니다.
눈치채신 분들도 계시겠지만, 연결리스트는 논리적으로는 연속적으로 데이터를 저장한 것처럼 보이지만, 물리적으로는 그렇지 않습니다.
데이터들이 메모리 공간 속 여기저기 떨어져 있고, 그것을 포인터로 연결한 것이죠.
위와 같은 방식으로 구현되었기 때문에 상대적으로 쉽게 데이터를 삽입하거나 삭제할 수 있습니다.
또한 가장 앞에 위치한 노드를 Head, 가장 뒤에 위치한 노드를 Tail이라고 합니다.
2. 장단점
장단점 또한 각 리스트 유형별로 조금씩 다르기 때문에 나눠서 설명하겠습니다.
2-1. 선형리스트
장점
- 빠른 조회 - 배열과 동일하게 인덱스를 사용하기 때문에 특정 값에 빠르게 접근할 수 있습니다.(O(1))
단점
- 삽입, 삭제 비용 - 삽입과 삭제가 일어나는 경우 리스트는 뒤의 데이터들을 모두 한칸씩 옮겨야 합니다. (O(n))
2-2. 연결리스트
장점
-
삽입, 삭제 용이 - 삽입, 삭제가 일어나는 경우 포인터가 가르키는 주소만 바꾸어 주면 되기 때문에 데이터 추가, 삭제가 용이합니다.
- 특정 값까지 순차적으로 이동해야하기 때문에 최악의 경우 O(n)의 시간복잡도를 가집니다.
-
연속적인 메모리를 사용하지 않기 때문에 크기를 미리 정할 필요가 없습니다.
- 선형리스트는 배열을 기반으로 만들어졌기 때문에 초기 크기가 정해지고, 초과되는 경우 내부적으로 다시 크기를 확장하는 방식으로 돌아갑니다.
단점
- 인덱스 접근 불가 - 인덱스의 개념이 없기 때문에 앞에서부터 순차적으로 따라가며 특정 값을 조회해야합니다. (O(n))
3. 구현
자바와 파이썬에서 리스트를 직접 사용해보겠습니다.
3-1. Java
선형리스트
//선형리스트
ArrayList list = new ArrayList<>();
list.add(1);
list.add("Hello");
//출력시 -> [1, "Hello"]
//0번째 인덱스 값 삭제
list.remove(0);
//출력시 -> ["Hello"]
//선형리스트에 저장되는 타입을 지정하는 경우
ArrayList<Integer> list2 = new ArrayList<>();
list2.add(1);
//list2.add("Hello") -> 불가위처럼 ArrayList 객체를 만들고 add()를 이용해서 값을 추가할 수 있습니다.
또한 remove()를 사용해서 인덱스에 해당하는 값을 삭제할 수 있습니다.
삭제 시, 뒤에 값이 한 칸 앞으로 이동하고 빈칸없이 출력되는 것을 확인할 수 있습니다.
자바를 사용해보신 분들은 아마 리스트에 값을 추가하기만 할 뿐 리스트의 크기에 관해서는 신경쓰지 않을 것 같습니다
그렇다면 크기가 정해져 있는 배열을 사용하면서 어떻게 크기를 확장할 수 있는 것일까요?
이는 Java 내부적으로 정해진 초기 배열의 크기(10) 를 초과하면 자동으로 배열의 크기가 늘어나도록 설계되어 있기 때문입니다.
add()를 따라가보면 위와같이 배열의 크기를 체크하는 메소드를 거치게 됩니다.
만약, 크기 제한에 걸리게 된다면(if문) grow() 를 수행하게 됩니다.
grow() 의 내부는 위와 같습니다.
새롭게 필요한 최소 용량 minCapacity와 기존 용량인 oldCapacity, oldCapacity를 통한 기본 증가용량 preferred growth를 통해 새로운 최적의 newCapacity를 도출합니다.
이후 기존 배열을 복사하여 크기가 확장된 배열을 얻을 수 있는 것이죠.
참고로 계속해서 크기를 늘리는 과정에서 메모리가 한정적인 경우, OutOfMemoryError를 던집니다
조금 정리가 되셨나요?
다음은 연결리스트입니다.
연결리스트
//연결리스트
LinkedList list = new LinkedList<>();
list.add(1);
list.add("Hello");
list.add(1, "java"); // 인덱스 1 위치에 데이터 삽입
//출력시 -> [1, "java", "Hello"]
//0번째 인덱스 값 삭제
list.remove(0);
//출력시 -> ["java", "Hello"]
//값 조회
list.get(1);
//출력시 -> "Hello"
//연결리스트에 저장되는 타입을 지정하는 경우
ArrayList<Integer> list2 = new ArrayList<>();
list2.add(1);
//list2.add("Hello") -> 불가위처럼 LinkedList 객체를 만들고 add() 메소드를 이용해서 원하는 인덱스 자리에값을 추가할 수 있습니다.
또한 remove() 메소드를 사용해서 인덱스에 해당하는 값을 삭제할 수 있습니다.
연결리스트의 다른 점인 조회 과정을 조금 더 살펴보겠습니다.
조회는 선형리스트와 마찬가지로 get() 를 통해 값을 조회합니다.
하지만 내부적으로 동작하는 방식은 조금 다릅니다.
get() 을 호출하면 위와같이 유효한 인덱스를 호출했는지 체크 후 node()메소드를 실행합니다.
살펴보면 첫번째 노드에 접근한 후, for문을 통해 호출한 인덱스까지 순차적으로 접근하는 것을 알 수 있습니다.
자바에서 리스트를 사용하는 방법과 조금 더 내부적으로 접근해서 알아보았습니다.
개인적으로 차이를 눈으로 확인하며 공부하니 재미있었습니다 하하~
다음은 파이썬입니다.
3-1. Python
파이썬은 비교적 간단합니다.
선형리스트
선형리스트는 배열 주제를 다룰 때 사용했던 것과 동일하게 사용됩니다.
#선형리스트
list = []
list.append(1)
list.append('hello')
# 출력시 -> [1, 'hello']
list.remove(1)
#출력시 -> ['hello']
#값과 함께 선언
list2 = [1, 2]위처럼 List 객체를 선언하고 append() 메소드를 이용해서 값을 추가할 수 있습니다.
또한 remove() 메소드를 사용해서 동일한 값을 찾아 삭제할 수 있습니다.
삭제 시, 뒤에 값이 한 칸 앞으로 이동하고 빈칸없이 출력되는 것을 확인할 수 있습니다.
연결리스트
파이썬에서는 만들어진 연결리스트 라이브러리가 없기 때문에 직접 구현해야합니다.
먼저 노드를 생성하는 클래스를 만들어줍니다.
#노드
class ListNode:
def __init__(self, val):
self.val = val
self.next = None이를 통해 노드를 생성하는 메소드를 만들어줍니다.
#연결리스트
class LinkedList:
def __init__(self, val):
self.head = ListNode(val)
def append(self, val):
cur = self.head
while cur.next:
cur = cur.next
cur.next = ListNode(val)
#원하는 위치에 노드 추가
def append_node(self, index, val):
new_node = ListNode(val)
#첫번째 자리라면
if index == 0:
new_node.next = self.head
self.head = new_node
return
cur = self.head
count = 0
while count < index:
count += 1
cur = cur.next
next_node = cur.next
cur.next = new_node
new_node.next = next_node이를 활용하여 파이썬에서 연결리스트를 사용할 수 있습니다.
#연결리스트
list = LinkedList(0)
list.append(5)
# 출력 시 -> [0, 5]
list.append_node(1, 'hello')
#출력 시 -> [0, 'hello', 5]한 번 직접 작성해보시면 더욱 이해가 빠르게 될 것 같습니다.
이상으로 리스트 자료구조에 대해서 알아보았습니다.
배열과 혼동될 수 있기 떄문에 천천히 뜯어보시는 걸 추천합니다!
오늘도 읽어주셔서 감사드리고, 다음 주제로 돌아오겠습니다!😝
References
