링크드 리스트

링크드 리스트는 리스트 List와 덱 Deque 등을 구현한 클래스입니다.
링크드 리스트에 대해 알아보기 전에 리스트와 덱에 대해 먼저 알아보았습니다. 

 

리스트  인터페이스

리스트 인터페이스는 순서가 있는 컬렉션으로 시퀀스 sequence 라고도 불립니다.
요소가 삽입될 위치를 조정할 수 있고, 인덱스로 요소에 접근할 수 있고, 리스트 내의 요소들을 검색할 수 있습니다.
아래 표는 각 기능을 구현한 메서드에 대한 설명입니다.

인덱스로 요소에 접근하는 메서드	구현한 클래스에 따라 요소를 인덱스로 접근하는데 인덱스의 값에 따라 실행 시간이 소요될 수 있습니다. (예: 링크드 리스트) get 메서드가 여기에 해당합니다.
리스트 내의 요소들을 검색하는 메서드	성능적인 면에서 주의해서 사용해야 하는데, 대부분의 구현 코드에서 실행시간이 선형적이기 때문입니다. lastIndexOf, indexOf 등의 메서드가 여기에 해당합니다.
위치에 따라 요소를 삽입하는 메서드	임의의 위치에 여러 요소를 삽입하고 삭제합니다. add(int index, E element), remove(index, E element)가 여기에 해당합니다.
리스트이터레이터 ListIterator	요소를 삽입하고, 대체하고, 양방향으로 접근할 수 있도록 하는 리스트 이터레이터 객체를 만들 수 있습니다. 이때 리스트 이터레이터는 리스트의 특정 위치에서 시작할 수 있습니다.

셋  Set 과 다르게 중복된 요소들(null 포함)을 허용합니다.

---

 

덱  인터페이스

덱 deque 은 queue 를 확장한 컬렉션 인터페이스로, double endeded queue라는 이름처럼 양 끝에서 요소를 삽입하고 삭제할 수 있습니다.
요소 삽입, 제거, 확인할 수 있는 메서드를 제공하며, 각 기능은 실패할 경우 예외를 일으키는 메서드와 null이나 false 등을 반환하는 메서드로 각각 제공됩니다. 후자의 경우 때문에, 덱의 null을 요소로 삽입하지 않기를 강력히 권장하고 있습니다.  

	앞 부분		끝 부분
	실패시 예외 발생	실패시 null 등 반환	실패시 예외 발생	실패시 null 등 반환
요소 삽입	addfirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
요소 제거	removeFirst()	pollFirst()	removeLast()	pollLast()
요소 확인	getFirst()	peekFirst()	getLast()	peekLast()

요소를 확인하는 메서드는 요소가 양 끝에 위치한 경우에만 가능하며, 인덱스를 통해 접근하는 메서드는 제공하지 않습니다. 

 

---

 

링크드 리스트

링크드 리스트는 리스트와 덱 등의 인터페이스를 구현한 클래스입니다.
링크드 리스트의 메서드는 컬렉션의 메서드와 함께, 앞선 리스트의 모든 메서드와 덱의 모든 메서드를 포함하고 있습니다.
링크드 리스트의 특징은 다음과 같습니다.

• 리스트 인터페이스의 모든 메서드를 구현했으며, null을 포함한 모든 타입을 요소로 가질 수 있습니다.
• 링크드 리스트의 모든 메서드는 덱 메서드 수준의 성능을 보이며,
  인덱스로 요소에 접근하는 경우 요소의 처음이나 끝에서 리스트를 순회합니다.
• 링크드 리스트는 동시성을 제공하지 않기 때문에, 멀티 스레드 환경에서는 List list = Collection.synchronizedList(new LinkedList(...)) 와 같이 감싸주어야합니다.
• 이터레이터 Iterator 를 생성한 후 remove나 add 와 같은 메서드를 호출해 리스트의 구조가 변경된다면, ConcurrentModificationException을 발생시킵니다.

 

---

Reference

List (Java Platform SE 8 )

 

Deque (Java Platform SE 8 )

 

LinkedList (Java Platform SE 8 )