리스트 자료구조 질문드립니다.

Question

리스트는 노드를 포인터로 연결한 자료구조라고 알고 있습니다.배열과 다르게 인덱스가 없어서 요소 접근에 대한 부분이 속도가 느리다고 알고 있는데요.java에서 list.get(int index) 라는 메서드의 파라미터 index가 있기 때문에, 리스트 자료구조는 인덱스가 존재하고, 요소 접근에 대한 단점도 없는 게 아닌가요?리스트 자료구조는 인덱스가 없는데, 리스트의 메서드에서는 인덱스를 파라미터를 가지니까 혼동이 되어 질문드립니다!

kiel · Accepted Answer

자바를 기준으로 List 는 인터페이스입니다. 구현체가 아닙니다. ArrayList 이냐 LinkedList 이냐에서 말씀하신 구현 차이가 납니다.말씀하신 자료구조는 엄밀하게는 LinkedList 입니다.List 의 index는 몇 번째 element 이냐를 가르키는 요소입니다. 리스트에 인덱스가 없다는게 어떤 의미인지 이해가 잘 안가네요. 참조 : https://docs.oracle.com/javase/8/docs/api/java/util/List.html

thlthl · Answer

Java list collection 종류에 따라 get()의 시간 복잡도가 다른 걸로 알고있는데 ArrayList의 경우 기존 배열과 같이 O(1)이며 LinkedList는 말씀하신대로 O(n)의 시간복잡도를 갖는게 맞습니다.

코딩두잇 · Answer

인덱스가 없는 건 set인터페이스 입니다List 계열은 순서를 가진 자료구조입니다

코딩두잇 · Answer

보통 List라 하면 Linked List를 말합니다.Array : 순차적이고 메모리 공간의 한곳에 모여있어 연속성을 가집니다Linked List : 순차적이지만 메모리 공간의 한곳에 모여있지 않아 연속성은 없습니다. 연결성은 있습니다.Array : 내부에 인덱스라는 검색방법을 사용해서 해당하는 번호의 데이터를 바로 찾아갑니다.get(100); ---> 100번방 검색시 인덱스를 통해서 100번방으로 직접 바로 갑니다.Linked List : 인덱스를 적용하지 않아서 처음방부터 시작해서 순서방까지 이동해서 찾습니다.get(100); ----> 100번방 검색시 1번방부터 시작해서 연결된 링크를 통해서 100번방까지 이동해갑니다.배열의 기능을 가지고 있는 List는 ArrayList입니다. list.get(int index) : int형의 index매개변수

리스트 자료구조 질문드립니다.

4개의 답변

#list 목록