LinkedList

LinkedList 의 특징

• 데이터 순서 있음 (index), 동일 데이터 중복 저장 허용
• Node로 구성
• Node는 데이터(data field)와 다음 Node의 주소(link field)로 구성
• Head는 첫번째 Node를 가리킴
• 마지막 Node의 링크 필드 값은 NULL
• 필요한 메모리를 동적할당해 사용하므로, 불필요한 메모리 낭비가 없음
• 비연속적 메모리 할당(ArrayList는 연속적인 메모리)
• ArrayList 보다 검색 느림
• ArrayList 보다 데이터 추가 삭제 빠름
  
  
  

LinkedList 선언

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.

LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능

LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능

LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능

LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

LinkedList 기본 메소드

LinkedList<Object> linkedList = new LinkedList<>();

리스트 크기 size()

linkedList.size();	//노드 개수 반환

데이터 추가 add(x), add(x, y)

linkedList.add(Object value);	//LinkedList의 마지막 위치에 value 추가
linkedList.add(int index, Object value);	//LinkedList 해당 index에 value 추가

데이터 삭제 remove(x), clear()

linkedList.remove(int index);	//index에 해당하는 데이터 제거
linkedList.claer();	//모든 데이터 제거

데이터 조회 get(x)

arrayList.get(int index);	//해당 index에 있는 데이터 가져옴

데이터 수정 set(x, y)

arryList.set(int index, Object value);	//해당 인덱스의 데이터 value로 변경

인덱스 조회 indexOf(x)

arrayList.indexOf(Object value);	//해당 값 없을 시 -1 반환

비어있는 리스트인지 확인 isEmpty()

arrayList.isEmpty();	//boolean값 반환

Doubly Linked List

• Doubly Linked List에서의 Node는 Previous field, Data field, 그리고 Next field가 있다.
• Singly Linked List(LinkedList)와 동일하지만, Previous field는 이전 Node의 주소가 있다.
• 즉, 양방향 탐색이 가능하다
• Doubly Linked List는 양쪽 끝 모두에 Null 포인터를 사용한다.