연결리스트(LinkedList)

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않음

자료 크기를 동적으로 조정 가능함에 따라 메모리를 효율적으로 사용할 수 있음

 

개별적으로 위치하는 각 원소를 노드의 링크 필드로 연결한다.

 

연결리스트는 헤드와 노드로 구성되어 있으며 Head는 Link만 존재하며 첫 노드에 대한 참조값을 가지고 있다.

Node는 원소값을 가지는 DATA 필드와 다음 노의 참조값을 가지는 LINK 필드로 이루어져 있다.

 

만약 노드의 링크 필드가 null이라면 해당 연결리스트의 마지막 원소라고 볼 수 있다.

 

노드를 중간에 삽입할 경우 유의할 사항

A와 C로 이루어진 연결 리스트 중간에 새로운 노드 B를 추가할 때, A 링크 필드에는 B의 주소값이 들어가고 B의 링크에는 C의 주소값을 넣어줘야 하는데 후자를 먼저 수행해야 한다. 그 이유는 전자를 먼저 수행할 경우, C의 주소값이 사라지기 때문이다.

 

 LinkedList<String> list = new LinkedList<>();

위와 같이 연결리스트를 구현할 수 있다.

 

주요 메서드

 

데이터 삽입 add / addFirst / push => 예외 발생 가능 (따라서 offer 메서드 사용추천)

list.add("b");
list.add(0,"a");

참고. 데이터 tail에 추가 => addLast

 

 

데이터 확인 get

System.out.println(list.get(0)); // "a" 출력

참고. getFirst, element, peek, peekLast 모두 첫번째값 출력, getLast 마지막 값 출력

 

 

데이터 변경 set

list.set(0, "z");

 

 

연결리스트 전체 출력 list

System.out.println(list); // [z, b]

 

 

데이터 첫번째 값 삭제: poll, pollFirst, pop, removeFirst

데이터 마지막 값 삭제: pollLast, removeLast

연결리스트의 크기: size

list.contains(1):  list에 1이 있는지 검색

list.indexOf(1): 1이 있는 index반환, 없으면 -1

 

 

 

** 이중 연결리스트는 데이터와 pre, next로 이루어져 있으며 pre는 앞 노드의 참조값을 next는 다음 노드의 참조값을 가진다.