[자료구조] Array와 LinkedList 개념 정리

김동욱·2023년 3월 16일
0

Java

목록 보기
1/8

배열(Arrays)

많은 수의 데이터를 다룰 때 사용하는 기본적인 자료구조이다.
배열을 구성하는 값 요소와 배열에서의 위치를 가리키는 숫자 인덱스로 구성되며 각 데이터를 인덱스와 1:1 대응한다.
데이터가 메모리 상에 연속적으로 저장된다.

장점

  • 인덱스를 통해 데이터에 빠르게 접근 가능 (1번인덱스나 130번 인덱스나 접근시간이 비슷하다)

단점

  • 참조 변경시에 기존 참조를 새로운 배열로 바꿔야 한다.
  • 미리 최대 길이를 정해서 생성하기 때문에 추가, 삭제가 번거롭다

예를 들어 크기를 변경하는 경우
1. 새로운 배열을 생성
2. 기존 내용을 복사
3. 배열 요소를 변경 후 다시 복사의 과정을 거치게 된다

위 문제들을 해결하기 위해 애초에 큰 배열을 만들면 메모리가 낭비된다.

Array 시간복잡도

접근검색삽입제거
O(1)O(n)O(n)O(n)

LinkedList

LinkedList는 데이터와 링크가 묶여있는 노드를 한 줄로 연결한 방식의 자료구조이며 각 링크는 다음 노드의 참조주소를 담고있다.

class Node{
Node next; //다음 노드
Object obj;// 데이터
}

한 번의 참조 변경으로 데이터의 삭제가 가능하며, 배열과는 달리 데이터 이동이 발생하지 않는다.
데이터의 참조만 변경해주면 기존의 데이터는 자동으로 사라지게 된다.
한 번의 Node 객체 생성과 두 번의 참조 변경으로 데이터를 추가할 수 있다.

단점

  • 연결 구조를 위한 별도 데이터 공간이 필요하다.
  • 데이터를 검색할 때 데이터 헤더에서부터 해당 데이터까지 순차적으로 탐색하기 때문에 데이터 접근성이 나쁘다.

LinkedList 시간복잡도

접근검색삽입제거
O(n)O(n)O(1)O(1)

더블리 링크드 리스트

class Node{
Node next; //다음 노드
Node previous; //이전 노드
Object obj;// 데이터
}

앞 뒤로 연결되어 접근성이 좋은 이중 연결 리스트이다.

더블리 써큘러 링크드 리스트

끝과 끝을 연결해준 이중 원형 연결 리스트

ArrayList (배열기반) vs LinkedList (연결기반)
순차적 추가,삭제 →ArrayList
접근시간 → ArrayList
중간에 추가,삭제 → LinkedList

profile
안녕하세요. 공부해요

0개의 댓글