[Data Structure] 싱글 링크드 리스트 (Singly LinkedList)
↘️바로가기
✨링크드리스트란?
이번 글에서는 싱글 링크드 리스트를 구현해 보겠다.
우선 ArrayList를 먼저 구현해 보고 학습해 보는 것을 권장한다.
https://0dedicated.tistory.com/49
싱글 링크드 리스트 (단순 연결 구조의 리스트)는 배열과 ArrayList와는 구조가 다르다.
연결된 구조 (Linked List)에서는 자료(데이터와, 링크값)를 노드에 담아 관리한다. 배열을 미리 선언하고 크기를 지정해 줄 필요가 없다. 필요할 때마다 노드를 생성해서 사용한다. 노드들은 메모리에 흩어져 존재하며 링크를 이용해 흩어진 노드들을 연결한다.
즉, ArrayList는 메모리에 순차적으로 순서 있게 저장되지만 LinkedList는 메모리에 흩어져 저장된다.
단순 연결 구조를 구현하기 위해 head, tail을 사용한다. head와 tail은 링크드 리스트의 시작과 끝을 가리키는 포인터이다.
LinkedList와 ArrayList의 차이점이 무엇일까?
LinkedList와 ArrayList 모두 순차적으로 저장하는 선형 자료구조이지만, 내부 구현과 방식, 성능에서 큰 차이점이 있다.
🔍 주요 차이점 ArrayList VS LinkedList
| 항목 | ArrayList | LinkedList |
| 구조 | 배열 기반 | 노드(Node) 기반 (각 노드는 값과 다음 노드 참조 혹은 주소값을 가짐) |
| 메모리 저장 방식 | 연속적인 메모리 공간에 저장 | 불연속적인 메모리 공간에 저장 |
| 접근속도(검색) | O(1) index로 접근 | O(n) 처음부터 끝까지 순차탐색 |
| 삽입/삭제(중간) | O(n) 데이터 이동 필수 | O(1) 참조(주소) 수정만 하면 됨 |
| 삽입/삭제(끝) | O(1) 동적 할당 시 O(n) | O(1) tail 있으면 없다면 O(n) |
| 메모리 사용 | 효율적 | 비효율적 (노드 생성할 때마다 오버헤드가 커짐) |
| 캐시 효율성 | 높음 (데이터 연속적으로 저장) | 낮음 (노드들이 흩어져 있음) |
무엇이 더 좋을까?
ArrayList 사용 유리할 때:
- 인덱스로 자주 접근할 때
- 데이터 크기가 거의 변하지 않을 때
- 메모리 효율성과 속도를 중요시할 때(읽기 중심)
LinkedList 사용 유리할 때:
- 삽입/삭제가 빈번하게 자주 발생할 때 (중간 삽입 포함)
- 데이터 크기가 자주 바뀌고 리스트 확장이 필요할 때
결론적으로 ArrayList는 검색에서 큰 강점이 보이고 LinkedList는 삽입/삭제 데이터를 자주 업데이트할 때 강점이 보인다.
개발자가 상황에 맞게 효율적인 자료구조를 선택하면 된다.
링크드 리스트는 스택, 큐, 덱에서도 응용이 가능하고 심화 자료구조를 학습하기 위해서 꼭 알아야 할 지식이다.
링크드 리스트는 앞으로 트리와 그래프 자료구조에서도 사용될 수 있으니 꼭 학습해야 한다.
단순 연결 구조 링크드 리스트를 구현하기 위해서는 Node라는 클래스를 만들어야 하고 리스트 연산자를 상속받아 구현할 예정이다.
또 타입의 안전성을 위해 제네릭을 사용하였다.
이번글에서 구현한 링크드 리스트는 단순 연결 구조이다.
✨리스트 인터페이스
리스트 인터페이스는 ArrayList, LinkedList 등 List에 공통된 연산자들을 묶음이다.
나중에 DoublyLinkedList 구현할 때도 리스트 인터페이스를 상속받을 것이다.
소스코드
package list;
public interface ListI<E> {
/**
* List 맨 앞에 요소를 추가합니다. (append)
*
* @param element 새롭게 추가되는 값
*/
public void addFirst(E element);
/**
* List 특정 index에 요소를 추가합니다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
*/
public void add(int index, E element);
/**
* List에 요소 추가 기본적으로 append 맨 뒤에 추가.
*
* @param element list에 삽입할 값
*/
public void add(E element);
/**
* List 맨 마지막에 요소를 추가합니다.
*
* @param element 새롭게 추가되는 값
*/
public void addLast(E element);
/**
* 특정 요소가 몇 번째 index에 존재하는지 반환하는 메서드
*
* @param element 찾고자 하는 값
* @return 찾았을 때 index값 반환
* 없다면 -1 반환
*/
public int indexOf(E element);
/**
* 특정 index에 요소 제거
*
* @param index 제거하고자 하는 특정 index값
* @return 제거한 값 반환
*/
public E remove(int index);
/**
*
*/
public E remove(E element);
/**
* 리스트가 공백 상태인지 확인하는 메서드
*
* @return 공백일 시 true 공백이 아닐 시 false
*/
public boolean isEmpty();
/**
* 리스트가 포화 상태인지 확인하는 메서드
*
* @return 포화일 시 true 포화가 아닐 시 false
*/
public boolean isFull();
/**
* 특정 index의 요소 반환
*
* @param index 찾을 위치 index
* @return 찾은 요소 반환
*/
public E get(int index);
/**
* 특정 index의 요소를 매개변수 요소로 변경하는 메서드
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
*/
public void set(int index, E element);
/**
* @param element
* @return element값이 리스트에 존재하면 true 아니면 false
*/
public boolean contains(E element);
/**
* 리스트에 존재하는 요소의 개수 반환
*
* @return 리스트의 총 용량
*/
public int size();
/**
* 리스트의 총 용량 반환.
*
* @return 리스트의 총 용량
*/
public int capacity();
}
노드 클래스
타입 안정성을 위해 제네릭을 사용하였다.
기본 생성자는 삭제해도 무방하며, data를 private로 외부 접근을 못하게 만들었다. data 접근은 getter를 사용해야 한다. data 수정은 setter를 사용한다. data를 public으로 바꾼다면 getter와 setter는 필요 없을 것이다.
package linkedlist;
public class Node<E> {
private E data;
public Node next;
Node() {
data = null;
next = null;
}
Node(E data) {
this.data = data;
next = null;
}
public void setData(E data) {
this.data = data;
}
public E getData() {
return data;
}
}
리스트 생성자와 필드
링크드 리스트는 노드 기반이므로 배열을 안 만들어도 된다.
필드로는
size: 노드의 개수 카운팅하는 변수
head: 리스트의 맨 앞부분을 가리키는 변수
tail: 리스트의 맨 뒤 부분을 가리키는 변수
LinkedList는 ArrayList와 달리 동적할당을 안 해도 된다.
public class SinglyLinkedList<E> implements ListI<E> {
private int size;
private Node<E> head;
private Node<E> tail;
/**
* 기본생성자.
*/
SinglyLinkedList() {
head = null;
tail = null;
size = 0;
}
search(int index)
LinkedList에서 add, remove 기능을 수행할 때 search 메서드는 큰 역할을 할 것이다.
search메서드는 꼭 필요하므로 먼저 만들자.
기능: 파라미터로 index값을 받는다. 받은 index로부터 List의 특정 부분(index)을 노드 객체로 반환하는 메서드이다.
파라미터 index값이 0보다 작고 size(노드 카운팅 변수) 보다 같거나 크면 예외를 던진다.
참고로 리스트의 노드 생성 후 size값을 업데이트하는 로직이다. (생성->size변수 업데이트)
/**
* 특정 index의 노드 반환하는 메서드
* <strong>찾는 과정</strong><br>
* 1. index가 0미만, size보다 같거나 크면 예외 발생 <br>
* 2. head 노드를 시작으로 반복문을 통해 index 값까지 순차적으로 탐색<br>
* O(N)
*
* @param index 찾고자하는 index값
* @return 예외 발생 안했으면 해당 index값의 node 반환
* @throws IndexOutOfBoundsException index 접근 잘못된 경우
*/
private Node<E> search(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
add 메서드들(추가)
LinkedList의 핵심적인 기능 삽입 연산(데이터 추가)이다.
add는 4가지 방식이다. addFirst(data), add(int index, data), add(data), addLast(data)
1. addFirst(E element)
리스트 맨 앞에 노드를 추가하는 메서드이다. 만약 리스트에 노드를 맨 처음 생성한다면 처음 생성한 노드의 링크(연결된 노드값)는 null을 가리킨다. (head가 맨 처음 초기화할 때 null이기 때문)
addFrist로직
1. 노드 생성
2. 노드 link head와 연결
3. 리스트에 생성한 노드가 방금 생성한 노드 1개뿐이면 tail도 방금 생성한 노드를 가리키도록 변경.
2. add(int index, E element)
리스트의 특정 index부분에 노드를 삽입하는 메서드이다. ArrayList는 중간 삽입 시 데이터 이동이 필요했지만 LinkedList는 가리키는 객체주소 값만 변경해 주면 된다.
add(int index) 로직
1. index 유효성 검사
2. index==0일 시 addFirst 호출 (어차피 맨 앞에 추가하는 거니깐)
3. index==size일 시 addLast 호출 (어차피 맨 뒤에 추가하는 거니깐)
4. search(index-1)로 특정 index 이 전 노드 가져오기
5. 이전 노드 다음 노드 (즉, 파라미터가 가리키는 기존(원래) index 노드 가져오기)
6. 노드 생성(새로운 노드)
7. 이전 노드 링크 새로운 노드와 연결
8. 새로운 노드 링크 이전 노드의 다음 노드 (원래 index에 존재했던 node)로 연결
9. size 업데이트
3. add(E element)
자바에서 제공하는 리스트들의 add 기본값은 addLast의 호출이다. 따라서 add(E element)는 addLast를 호출한다.
append() 느낌이다.
4. addLast(E element)
리스트의 맨 끝에 노드를 생성하는 메서드이다.
addLast로직
1. size==0 이면 리스트에 노드 하나도 없는 상태이니 addFirst 호출
2. 노드 생성(새로운 노드)
3. 기존에 tail이 가리키던 노드의 링크 새로운 노드로 변경
4. tail 새로운 노드 가리키게 변경
5. size 변수 업데이트
소스코드 (길어서 접은 글)
/**
* 리스트 맨 앞에 요소를 추가,
* 처음 추가한 요소는 링크값(연결된 노드값)은 null이다. head가 null이므로
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
Node<E> node = new Node<>(element);
node.next = head;
head = node;
if (size == 0) {
tail = node;
}
size++;
}
/**
* 리스트 특정 index부분에 요소를 추가하는 메서드
* 특정 index 이 전 노드는 새로운 노드와 연결하고 새로운 노드는 특정 index 이 후 노드와 연결
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
addLast(element);
return;
}
Node<E> prevNode = search(index - 1);
Node<E> nextNode = prevNode.next;
Node<E> newNode = new Node<E>(element);
prevNode.next = newNode;
newNode.next = nextNode;
size++;
}
/**
* add method는 기본적으로 addLast 호출
* Java 공식적인 LinkedList도 맨 뒤 요소 추가가 기본이다.
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
}
/**
* 리스트에서 추가할 수 있는 맨 마지막 부분에 요소를 추가한다.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addLast(E element) {
if (size == 0) {
addFirst(element);
return;
}
Node<E> node = new Node<>(element);
tail.next = node;
tail = node;
size++;
}
remove 메서드들(삭제)
삽입보다 삭제 코드가 더 복잡할 수 있다.
remove는 remove(), remove(index), remove(data) 삭제 방법은 3개가 존재한다.
1.remove()
head가 가리키는 요소를 삭제하는 메서드이다.
리스트의 맨 앞 요소를 삭제하는 메서드라고 볼 수 있다.
remove() 로직
1. size가 0보다 작거나 같으면 null 반환
2. head가 가리키는 노드 가져오기
3. head가 가리키는 노드 링크 노드 가져오기
4. head가 가리키는 노드 요소 값 꺼내서 따로 변수에 저장 (나중에 반환해야 하므로)
5. head를 기존 head가 가리키는 노드 링크 노드로 바꾸기
6. size값 감소 만약 size값이 0이면 리스트 공백 상태이므로 tail에 null로 대입
2.remove(int index)
리스트의 특정 위치(index) 요소를 삭제하는 메서드이다.
parameter 값은 특정 위치 (index)이다.
remove(int index) 로직
1. index 유효성 검사 만약 index==0 이면 remove() 호출
2. search 메서드로 index-1 노드 가져오기
3. index-1 노드의 링크 노드 가져오기
4. index-1 노드 링크를 index노드의 링크 노드로 연결하기 A - B - C 였으면 A - C로 연결
5. index 노드 데이터 값 변수에 따로 저장(반환해야 하므로)
6. size값 줄이기, index-1 노드가 null을 가리키게 된다면 tail을 index-1을 가리키게 한다.
3. remove(E element)
리스트의 특정 요소(value)를 리스트에서 찾아 해당되는 노드를 삭제하는 메서드이다.
좀 복잡할 수 있지만, 다른 분들이 더 깔끔히 구현한 것도 많을 수 있으므로 많이 찾아보길 바란다.
remove(E element) 로직
1. 리스트 공백상태 확인 공백이면 null반환
2. index=0부터 반복문을 통해 리스트를 순차방문한다. 여기서 노드의 요소값을 equals로 비교한다.
3. equals 결과 true이면 break를 통해 반복문에서 나온다. 더 이상 노드의 링크가 존재하지 않으면 반복문에서 나온다.
4. index>=size이면 index가 모든 노드를 방문하였지만 특정 요소가 없는 것이므로 null반환
5. equals true일 때, 노드가 head랑 같다면 remove() 호출
6. 특정 요소가 존재하는 노드의 이전 노드 가져오기 search(index-1)
7. index-1 노드 특정 요소를 지닌 노드의 링크 노드로 연결
8. 특정 요소값 변수에 따로 저장
9. size값 감소 size==1 이면 리스트에 노드 하나이므로 tail 하나 남은 노드 가리키게 한다.
remove 소스코드
/**
* 맨 앞 head가 가리키는 노드를 삭제하는 메서드이다.
*
* @return 삭제된 data값
*/
public E remove() {
if (size <= 0) {
return null;
}
Node<E> headNode = head;
Node<E> headNextNode = headNode.next;
E returnData = headNode.getData();
head = headNextNode;
size--;
if (size == 0) {
tail = null;
}
return returnData;
}
/**
* 리스트의 특정 index의 요소를 삭제 후 요소의 데이터값 반환하는 메서드이다.
*
* @param index 제거하고자 하는 특정 index값
* @return index==0 일 시 기본 remove() 호출 삭제한 데이터 값 반환
* @throws IndexOutOfBoundsException
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E returnData = null;
if (index == 0) {
return remove();
}
Node<E> prevNode = search(index - 1);
Node<E> deleteNode = prevNode.next;
prevNode.next = deleteNode.next;
returnData = deleteNode.getData();
deleteNode.next = null;
size--;
if (prevNode.next == null) {
tail = prevNode;
}
return returnData;
}
/**
* 리스트의 특정 data값과 일치하는 요소를 삭제하는 메서드이다.
*
* @param element 삭제하고자 하는 데이터 값
* @return 삭제한 값 반환
*/
@Override
public E remove(E element) {
if (isEmpty()) {
System.out.println("리스트가 빈 상태이다.");
return null;
}
int index = 0;
Node<E> node = head;
while (node != null) {
if (node.getData().equals(element)) {
break;
}
node = node.next;
index++;
}
if (index >= size) {
System.out.println(element + "는 리스트에 존재하지 않습니다.");
return null;
}
if (node.equals(head)) {
return remove();
}
Node<E> prevNode = search(index - 1);
prevNode.next = node.next;
E data = node.getData();
node.next = null;
node.setData(null);
System.out.println("삭제한 값 " + data);
size--;
if (size == 1) {
tail = prevNode;
}
return data;
}
isEmpty, isFull
리스트의 공백과 포화상태를 검사하는 기능이다.
참고로 연결된 구조의 리스트는 가변적 크기의 특성이 있어 메모리 누수 상태가 아닌 이상 포화상태는 존재하지 않는다.
공백: size <=0
포화: false(포화상태 존재하지 않는다고 가정)
/**
* size는 add, remove 기능 수행할 때마다 size값을 업데이트한다.
* 이 때 size값이 0보다 작거나 같다면 리스트에 노드가 하나도 없는 상태이므로
* 공백상태이다.
*
* @return size<= 0 이 true이면 공백 false이면 공백상태가 아님
*/
@Override
public boolean isEmpty() {
return size <= 0;
}
/**
* 동적 할당이므로 포화 상태는 존재하지 않는다.
* 메모리 누수일 시 포화이다.
*
* @return 기본 false
*/
@Override
public boolean isFull() {
return false;
}
indexOf(target), contains(target)
리스트의 특정 노드를 검색하는 메서드들이다
indexOf는 특정 요소값을 지닌 노드의 index값을 반환하는 메서드
contains는 특정 요소값을 지닌 노드의 데이터 값을 반환하는 메서드
indexOf = index 값
contains = 데이터 값
/**
* 찾고자하는 element 값을 index0~n까지 순차적으로 검색하는 메서드
*
* @param element 찾고자 하는 값
* @return -element 찾았을 경우 index값 반환, 못 찾을 경우 -1 반환
*/
@Override
public int indexOf(E element) {
Node<E> headNode = head;
for (int i = 0; i < size; i++, headNode = headNode.next) {
if (element.equals(headNode.getData())) {
return i;
}
}
return -1;
}
/**
* @param element
* @return
*/
@Override
public boolean contains(E element) {
Node<E> headNode = head;
while (headNode != null) {
if (headNode.getData().equals(element)) {
return true;
}
headNode = headNode.next;
}
return false;
}
get(int index), set(index, E element)
get은 특정 위치의 노드 요소값 반환
set은 특정 위치의 노드 요소값을 파라미터 element값으로 변경
get = 조회
set = 수정
/**
* 리스트의 특정 위치의 노드의 데이터 값을 반환하는 메서드이다.
* @param index 찾을 위치 index
* @return
* @throws IndexOutOfBoundsException
*/
@Override
public E get(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> searchNode = search(index);
System.out.println(index + "번째에 꺼낸 데이터: " + searchNode.getData());
return searchNode.getData();
}
/**
* 리스트의 특정 위치의 노드의 데이터 값을 parameter 값으로 변경하는 메서드이다.
* 리스트의 특정 위치의 노드 요소값 변경 기능.
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
* @throws IndexOutOfBoundsException
*/
@Override
public void set(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> node = search(index);
node.setData(element);
}
각 종 메서드들 (크기, 출력 등)
각 종 유틸리티 메서드이다.
필요에 따라 더 구현하거나 리팩터링 하여 만들 수 있다.
/**
* 리스트에 존재하는 노드의 개수 반환하는 메서드
* @return 노드의 개수
*/
@Override
public int size() {
return size;
}
/**
* 리스트의 총 용량을 반환하는 메서드 연결된 구조에서는
* 총 용량은 제한되지 않는다.
* @return
*/
@Override
public int capacity() {
return size;
}
/**
* 리스트의 데이터들을 Object[] 배열에 담아 문자열로 반환하는 메서드이다.
* 리스트의 상태를 보기 쉽게 하기 위한 메서드이다.
*
* @return 가변 스트링을 반환한다.
*/
public StringBuilder toArray() {
Object[] arr = new Object[size];
StringBuilder sb = new StringBuilder().append("[");
Node<E> headNode = head;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(headNode.getData() + ",");
} else {
sb.append(headNode.getData() + "]");
}
headNode = headNode.next;
}
return sb;
}
✨전체 코드 (SinglyLinkedList )
package linkedlist;
import list.ListI;
/**
* Singly LinkedList 구현
*
* @param <E> 제네릭 객체 사용 (객체만 저장 가능)
*/
public class SinglyLinkedList<E> implements ListI<E> {
private int size;
private Node<E> head;
private Node<E> tail;
/**
* 기본생성자.
*/
SinglyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* 특정 index의 노드 반환하는 메서드
* <strong>찾는 과정</strong><br>
* 1. index가 0미만, size보다 같거나 크면 예외 발생 <br>
* 2. head 노드를 시작으로 반복문을 통해 index 값까지 순차적으로 탐색<br>
* O(N)
*
* @param index 찾고자하는 index값
* @return 예외 발생 안했으면 해당 index값의 node 반환
* @throws IndexOutOfBoundsException index 접근 잘못된 경우
*/
private Node<E> search(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 리스트 맨 앞에 요소를 추가,
* 처음 추가한 요소는 링크값(연결된 노드값)은 null이다. head가 null이므로
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
Node<E> node = new Node<>(element);
node.next = head;
head = node;
if (size == 0) {
tail = node;
}
size++;
}
/**
* 리스트 특정 index부분에 요소를 추가하는 메서드
* 특정 index 이 전 노드는 새로운 노드와 연결하고 새로운 노드는 특정 index 이 후 노드와 연결
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
addLast(element);
return;
}
Node<E> prevNode = search(index - 1);
Node<E> nextNode = prevNode.next;
Node<E> newNode = new Node<E>(element);
prevNode.next = newNode;
newNode.next = nextNode;
size++;
}
/**
* add method는 기본적으로 addLast 호출
* Java 공식적인 LinkedList도 맨 뒤 요소 추가가 기본이다.
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
}
/**
* 리스트에서 추가할 수 있는 맨 마지막 부분에 요소를 추가한다.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addLast(E element) {
if (size == 0) {
addFirst(element);
return;
}
Node<E> node = new Node<>(element);
tail.next = node;
tail = node;
size++;
}
/**
* 찾고자하는 element 값을 index0~n까지 순차적으로 검색하는 메서드
*
* @param element 찾고자 하는 값
* @return -element 찾았을 경우 index값 반환, 못 찾을 경우 -1 반환
*/
@Override
public int indexOf(E element) {
Node<E> headNode = head;
for (int i = 0; i < size; i++, headNode = headNode.next) {
if (element.equals(headNode.getData())) {
return i;
}
}
return -1;
}
/**
* 맨 앞 head가 가리키는 노드를 삭제하는 메서드이다.
*
* @return 삭제된 data값
*/
public E remove() {
if (size <= 0) {
return null;
}
Node<E> headNode = head;
Node<E> headNextNode = headNode.next;
E returnData = headNode.getData();
head = headNextNode;
size--;
if (size == 0) {
tail = null;
}
return returnData;
}
/**
* 리스트의 특정 index의 요소를 삭제 후 요소의 데이터값 반환하는 메서드이다.
*
* @param index 제거하고자 하는 특정 index값
* @return index==0 일 시 기본 remove() 호출 삭제한 데이터 값 반환
* @throws IndexOutOfBoundsException
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E returnData = null;
if (index == 0) {
return remove();
}
Node<E> prevNode = search(index - 1);
Node<E> deleteNode = prevNode.next;
prevNode.next = deleteNode.next;
returnData = deleteNode.getData();
deleteNode.next = null;
size--;
if (prevNode.next == null) {
tail = prevNode;
}
return returnData;
}
/**
* 리스트의 특정 data값과 일치하는 요소를 삭제하는 메서드이다.
*
* @param element 삭제하고자 하는 데이터 값
* @return 삭제한 값 반환
*/
@Override
public E remove(E element) {
if (isEmpty()) {
System.out.println("리스트가 빈 상태이다.");
return null;
}
int index = 0;
Node<E> node = head;
while (node != null) {
if (node.getData().equals(element)) {
break;
}
node = node.next;
index++;
}
if (index >= size) {
System.out.println(element + "는 리스트에 존재하지 않습니다.");
return null;
}
if (node.equals(head)) {
return remove();
}
Node<E> prevNode = search(index - 1);
prevNode.next = node.next;
E data = node.getData();
node.next = null;
node.setData(null);
System.out.println("삭제한 값 " + data);
size--;
if (size == 1) {
tail = prevNode;
}
return data;
}
/**
* size는 add, remove 기능 수행할 때마다 size값을 업데이트한다.
* 이 때 size값이 0보다 작거나 같다면 리스트에 노드가 하나도 없는 상태이므로
* 공백상태이다.
*
* @return size<= 0 이 true이면 공백 false이면 공백상태가 아님
*/
@Override
public boolean isEmpty() {
return size <= 0;
}
/**
* 동적 할당이므로 포화 상태는 존재하지 않는다.
* 메모리 누수일 시 포화이다.
*
* @return 기본 false
*/
@Override
public boolean isFull() {
return false;
}
/**
* 리스트의 특정 위치의 노드의 데이터 값을 반환하는 메서드이다.
*
* @param index 찾을 위치 index
* @return
* @throws IndexOutOfBoundsException
*/
@Override
public E get(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> searchNode = search(index);
System.out.println(index + "번째에 꺼낸 데이터: " + searchNode.getData());
return searchNode.getData();
}
/**
* 리스트의 특정 위치의 노드의 데이터 값을 parameter 값으로 변경하는 메서드이다.
* 리스트의 특정 위치의 노드 요소값 변경 기능.
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
* @throws IndexOutOfBoundsException
*/
@Override
public void set(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> node = search(index);
node.setData(element);
}
/**
* @param element
* @return
*/
@Override
public boolean contains(E element) {
Node<E> headNode = head;
while (headNode != null) {
if (headNode.getData().equals(element)) {
return true;
}
headNode = headNode.next;
}
return false;
}
/**
* 리스트에 존재하는 노드의 개수 반환하는 메서드
*
* @return 노드의 개수
*/
@Override
public int size() {
return size;
}
/**
* 리스트의 총 용량을 반환하는 메서드 연결된 구조에서는
* 총 용량은 제한되지 않는다.
*
* @return
*/
@Override
public int capacity() {
return size;
}
/**
* 리스트의 데이터들을 Object[] 배열에 담아 문자열로 반환하는 메서드이다.
* 리스트의 상태를 보기 쉽게 하기 위한 메서드이다.
*
* @return 가변 스트링을 반환한다.
*/
public StringBuilder toArray() {
Object[] arr = new Object[size];
StringBuilder sb = new StringBuilder().append("[");
Node<E> headNode = head;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(headNode.getData() + ",");
} else {
sb.append(headNode.getData() + "]");
}
headNode = headNode.next;
}
return sb;
}
}
문제 있는 부분 댓글 달아주세요!