자바의 정석 11장 (28일차) - LinkedList

LinkedList 

일반 배열

장점: 구조가 간단하고 데이터를 읽는데 걸리는 시간이 짧다.

단점: 크기 변경이 불가능하기때문에 새로운 배열을 생성하고 기존내용을 그 배열로 복사해야한다.

단점2: 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

• 데이터를 추가하거나 삭제하면 나머지 데이터를 복사하여 움직이는 시간때문.
• 비순차적인 데이터 삭제 시:
  • remove함수를 사용하여 index를 뒤에서부터 지정하고 데이터를 옮기는 작업을 생략

LinkedList는 위의 단점들을 보완하여 나온 클래스

 

배열이 연속적으로 존재하는 데이터를 연결한 집합이라면, LinkedList는 불연속적으로 존재하는 데이터를 연결한 집합.

따라서 배열은 한 데이터를 추가하려면 모든 데이터를 옮겨야 가능하지만, LinkedList는 개별요소를 연결해놓았기 때문에 연결에 용이하다

 

위의 이유로, 삭제에도 용이

 

단점: 불연속적이기 때문에 데이터 접근이 힘들다.

• 첫번째 데이터는 두번째 데이터랑 연결되어있기 때문에 두번째는 알지만 3번째부터는 모른다.
• 3번째에 접근하려면 두번째로 이동해야 접근 가능

 

단점을 보완하려고 만든 새로운 클래스: doublylinkedlist

 

연결이 1개만 되어있지않고 앞뒤로 2개가 되어있는 클래스

• 앞뒤로 연결이 되어있기 때문에 앞뒤 1칸씩 이동이 가능하지만, 여전히 2칸 이상은 불가능하다.
• 삭제, 삽입을 할 때 2개의 연결을 맺어줘야 하는 불편함

---

총정리!

효율적으로 쓸 수 있는 조건

순차적인 삭제, 추가 + 접근성: ArrayList

비순차적인 삭제, 추가: LinkedList