[Data Structure] List

[2d3k]

1. Linkedlist

2. ArrayList

3. 둘의 시간복잡도 차이는?

[2d3k]

1 LinkedList: 연결 리스트를 이용하여 데이터를 저장합니다. 데이터의 삽입, 삭제시 다른 요소들의 이동이 필요하지 않기 때문에 빠른 속도를 보일 수 있습니다. 하지만 인덱스를 이용하여 요소에 접근하기 위해서는 리스트를 순회해야 하므로 ArrayList보다 느린 속도를 보일 수 있습니다. 데이터의 삽입, 삭제가 빈번하게 일어나는 경우에 적합하다.

2 ArrayList: 내부적으로 배열을 이용하여 데이터를 저장합니다. 데이터의 삽입, 삭제시 다른 요소들의 이동이 필요하기 때문에 느린 속도를 보일 수 있습니다. 하지만 인덱스를 이용하여 요소에 빠르게 접근할 수 있으며 데이터의 순회에는 적합합니다. 데이터의 접근 및 순회가 빈번하게 일어나는 경우에 적합하다.

3 ArrayList는 내부적으로 배열을 사용하기 때문에 인덱스를 이용하여 요소에 빠르게 접근할 수 있습니다. 따라서, 요소 접근의 시간 복잡도는 O(1)입니다. 하지만, 중간에 요소를 삽입하거나 삭제할 경우 다른 요소들을 이동시켜야 하므로 시간 복잡도가 O(n)입니다. 또한 요소를 검색할 경우에도 배열을 순회해야 하므로 시간 복잡도가 O(n)입니다.

LinkedList는 요소들을 연결하여 구현하기 때문에 인덱스를 이용하여 요소에 접근하기 위해서는 리스트를 순회해야 합니다. 따라서, 요소 접근의 시간 복잡도는 O(n)입니다. 하지만, 중간에 요소를 삽입하거나 삭제할 경우 이전 요소나 다음 요소와의 연결만 변경하면 되기 때문에 시간 복잡도가 O(1)입니다. 또한 요소를 검색할 경우에도 리스트를 순회해야 하므로 시간 복잡도가 O(n)입니다.

[hyeonayou]

1. 데이터들이 자료의 주소 값으로 서로 연결되어 있는 구조 ( 노드가 서로 연결되어 있는 형태) LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.

2. 데이터들이 순서대로 쭉 늘어선 배열의 형식을 취하고 있음 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.

get() : arryList o(1) , Linked List o(n) add() : o(1) , o(1) remove() : o(n), o(n)