본문 바로가기
Programming/Algorithm&DataStructure

[JAVA 자료구조] Singly LinkedList (단일 연결리스트)

by prinha 2021. 8. 5.
728x90
반응형

Singly LinkedList

배열이 아닌 '노드'를 이용하여 여러 노드를 하나의 체인처럼 단방향으로 연결한 리스트

 

node : 다른 노드를 가리킬 주소데이터를 담은 객체

 

배열과 연결리스트의 차이

(위 그림에서 각각의 레퍼런스 변수는 다음 노드객체를 가리키고 있음)

이미지 출처 : https://st-lab.tistory.com/167

 

더보기

 

package Interface_form;
 
/**
 * 
 * 자바 List Interface입니다. <br>
 * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this list
 *
 * @version 1.0
 * 
 */
 
public interface List<E> {
 
	/**
	 * 리스트에 요소를 추가합니다.
	 * 
	 * @param value 리스트에 추가할 요소
	 * @return 리스트에서 중복을 허용하지 않을 경우에 리스트에 이미 중복되는 
	 *         요소가 있을 경우 {@code false}를 반환하고, 중복되는 원소가
	 *         없을경우 {@code true}를 반환
	 */
	boolean add(E value);
 
	/**
	 * 리스트에 요소를 특정 위치에 추가합니다. 
	 * 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
	 * 
	 * @param index 리스트에 요소를 추가할 특정 위치 변수
	 * @param value 리스트에 추가할 요소
	 */
	void add(int index, E value);
 
	/**
	 * 리스트의 index 위치에 있는 요소를 삭제합니다.
	 * 
	 * @param index 리스트에서 삭제 할 위치 변수
	 * @return 삭제된 요소를 반환
	 */
	E remove(int index);
 
	/**
	 * 리스트에서 특정 요소를 삭제합니다. 동일한 요소가 
	 * 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
	 * 
	 * @param value 리스트에서 삭제할 요소
	 * @return 리스트에 삭제할 요소가 없거나 삭제에 실패할 
	 *         경우 {@code false}를 반환하고 삭제에 성공할 경우 {@code true}를 반환 
	 */
	boolean remove(Object value);
 
	/**
	 * 리스트에 있는 특정 위치의 요소를 반환합니다.
	 * 
	 * @param index 리스트에 접근할 위치 변수 
	 * @return 리스트의 index 위치에 있는 요소 반환 
	 */
	E get(int index);
 
	/**
	 * 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
	 * 
	 * @param index 리스트에 접근할 위치 변수 
	 * @param value 새로 대체할 요소 변수 
	 */
	void set(int index, E value);
 
	/**
	 * 리스트에 특정 요소가 리스트에 있는지 여부를 확인합니다.
	 * 
	 * @param value 리스트에서 찾을 특정 요소 변수 
	 * @return 리스트에 특정 요소가 존재할 경우 {@code true}, 존재하지 않을 경우 {@code false}를 반환  
	 */
	boolean contains(Object value);
 
	/**
	 * 리스트에 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
	 * 
	 * @param value 리스트에서 위치를 찾을 요소 변수  
	 * @return 리스트에서 처음으로 요소와 일치하는 위치를 반환.
	 *         만약 일치하는 요소가 없을경우 -1 을 반환 
	 */
	int indexOf(Object value);
 
	/**
	 * 리스트에 있는 요소의 개수를 반환합니다.
	 * 
	 * @return 리스트에 있는 요소 개수를 반환  
	 */
	int size();
 
	/**
	 * 리스트에 요소가 비어있는지를 반환합니다.
	 * @return 리스트에 요소가 없을경우 {@code true}, 요소가 있을경우 {@code false}를 반환 
	 */
	boolean isEmpty();
 
	/**
	 * 리스트에 있는 요소를 모두 삭제합니다.
	 */
	public void clear();
 
}

 


0. Node 구현 (Node.java)

class Node<E> {
 
	E data;
	Node<E> next;	// 다음 노드객체를 가리키는 래퍼런스 변수
 
	Node(E data) {
		this.data = data;
		this.next = null;
	}
}

 

1) Node<E> next

Reference 변수(다음 노드를 가리키는 변수)로 노드 자체를 가리키기 때문에 Node<E>타입으로 지정해줌

 

 

1. 클래스 및 생성자 구성

import Interface_form.List;
 
public class SLinkedList<E> implements List<E> {
 
	private Node<E> head;	// 노드의 첫 부분 
	private Node<E> tail;	// 노드의 마지막 부분
	private int size;	// 요소 개수 
 
	// 생성자
	public SLinkedList() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
}

 

1) Node<E> head : 리스트의 가장 첫 노드를 가리키는 변수

2) Node<E> tail : 리스트의 가장 마지막 노드를 가리키는 변수

3) sizd : 리스트에 연결된 노드의 개수

 

처음 연결리스트를 생성할 때에는 데이터가 없으므로 null, 0으로 초기화 진행

// 메인클래스에서 객체 생성 시
SLinkedList<Integer> list = new SLinkedList<>();

 

 

2. Search

// 특정 위치의 노드를 반환하는 메소드
private Node<E> search(int index) {
		
	// 범위 밖(잘못된 위치)일 경우 예외 던지기 
	if(index < 0 || index >= size) {
		throw new IndexOutOfBoundsException();
	}
		
	Node<E> x = head;	// head가 기리키는 노드부터 시작 
		
	for (int i = 0; i < index; i++) {
		x = x.next;	// x노드의 다음 노드를 x에 저장한다
	}
	return x;
}

데이터의 삽입, 삭제, 검색을 위해서는 처음 노드부터 next변수를 통해 이동해야 한다.

노드의 데이터 X 노드 자체 반환

 

3. add

public void addFirst(E value) {
 
	Node<E> newNode = new Node<E>(value);	// 새 노드 생성
	newNode.next = head;	// 새 노드의 다음 노드로 head 노드를 연결
	head = newNode;	// head가 가리키는 노드를 새 노드로 변경
	size++;
 
	/**
	 * 다음에 가리킬 노드가 없는 경우(=데이터가 새 노드밖에 없는 경우)
	 * 데이터가 한 개(새 노드)밖에 없으므로 새 노드는 처음 시작노드이자
	 * 마지막 노드다. 즉 tail = head 다.
	 */
	if (head.next == null) {
		tail = head;
	}
}
	
@Override
public boolean add(E value) {
	addLast(value);
	return true;
}
 
public void addLast(E value) {
	Node<E> newNode = new Node<E>(value);	// 새 노드 생성 
 
	if (size == 0) {	// 처음 넣는 노드일 경우 addFisrt로 추가
		addFirst(value);
		return;
	}
 
	/**
	 * 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 하고
	 * tail이 가리키는 노드를 새 노드로 바꿔준다. 
	 */
	tail.next = newNode;
	tail = newNode;
	size++;
}
 
@Override
public void add(int index, E value) {
 
	// 잘못된 인덱스를 참조할 경우 예외 발생
	if (index > size || index < 0) {
		throw new IndexOutOfBoundsException();
	}
	// 추가하려는 index가 가장 앞에 추가하려는 경우 addFirst 호출 
	if (index == 0) {
		addFirst(value);
		return;
	}
	// 추가하려는 index가 마지막 위치일 경우 addLast 호출
	if (index == size) {
		addLast(value);
		return;
	}
		
	// 추가하려는 위치의 이전 노드 
	Node<E> prev_Node = search(index - 1);
	
	// 추가하려는 위치의 노드
	Node<E> next_Node = prev_Node.next;
 
	// 추가하려는 노드
	Node<E> newNode = new Node<E>(value);	
		
	/**
	 * 이전 노드가 가리키는 노드를 끊은 뒤
	 * 새 노드로 변경해준다. 
	 * 또한 새 노드가 가리키는 노드는 next_Node로
	 * 설정해준다. 
	 */
	prev_Node.next = null;
	prev_Node.next = newNode;
	newNode.next = next_Node;
	size++;
 
}

 

1) 첫번째 위치 삽입 : addFirst(E value)

이미지 출처 : https://st-lab.tistory.com/167

데이터를 이동시키는 것이 아닌 새로운 노드를 생성하고 새 노드의 레퍼런스 변수가 head노드를 가리키도록 한다.

 

2) 기본(마지막 위치) 삽입 : addLast(E value)

이미지 출처 : https://st-lab.tistory.com/167

size=0일 경우(아무런 노드가 없는 경우)는 처음으로 데이터를 추가한다는 뜻이므로 addFirst()를 호출한다.

데이터를 이동시키는 것이 아닌 새로운 노드를 생성하고 이전 노드의 레퍼런스 변수가 새로운 노드를 가리키도록 한다.

 

3) 특정 위치에 추가 : add(int index, E value)

이미지 출처 : https://st-lab.tistory.com/167

(넣으려는 위치의 앞 뒤로 링크를 새로 업데이트를 해주어야 하기 때문에 할 일이 가장 많다.)

 

- 넣으려는 위치의 이전 노드를 prev_Node라 하고, 넣으려는 위치의 기존 노드를 next_Node라고 칭한다.

- Search() 메소드를 이용하여 넣으려는 위치의 -1 노드(prev_Node)를 찾아내고, next_Node는 prev_Node.next를 통해 찾는다.

- prev_Node()의 링크를 새로 추가하려는 노드로 변경하고, 새로 추가하는 노드의 링크는 next_Node로 변경한다.

- index변수가 잘못된 위치를 참조할 수 있기 때문에 IndexOutOfBoundException예외처리를 해준다.

 

 

 

4. remove

public E remove() {
 
	Node<E> headNode = head;
 
	if (headNode == null)
		throw new NoSuchElementException();
		
	// 삭제된 노드를 반환하기 위한 임시 변수
	E element = headNode.data;
		
	// head의 다음 노드 
	Node<E> nextNode = head.next;
		
	// head 노드의 데이터들을 모두 삭제
	head.data = null;
	head.next = null;
		
	// head 가 다음 노드를 가리키도록 업데이트
	head = nextNode;
	size--;
		
	/**
	 * 삭제된 요소가 리스트의 유일한 요소였을 경우
	 * 그 요소는 head 이자 tail이었으므로 
	 * 삭제되면서 tail도 가리킬 요소가 없기 때문에
	 * size가 0일경우 tail도 null로 변환
	 */
	if(size == 0) {
		tail = null;
	}
	return element;
}
 
@Override
public E remove(int index) {
 
	// 삭제하려는 노드가 첫 번째 원소일 경우 
	if (index == 0) {
		return remove();
	}
 
	// 잘못된 범위에 대한 예외 
	if (index >= size || index < 0) {
		throw new IndexOutOfBoundsException();
	}
		
	Node<E> prevNode = search(index - 1);	// 삭제할 노드의 이전 노드 
	Node<E> removedNode = prevNode.next;	// 삭제할 노드 
	Node<E> nextNode = removedNode.next;	// 삭제할 노드의 다음 노드 
 
	E element = removedNode.data;	// 삭제되는 노드의 데이터를 반환하기 위한 임시변수
	
	// 이전 노드가 가리키는 노드를 삭제하려는 노드의 다음노드로 변경 
	prevNode.next = nextNode;
		
	// 데이터 삭제 
	removedNode.next = null;
	removedNode.data = null;
	size--;
 
	return element;
}
 
@Override
public boolean remove(Object value) {
 
	Node<E> prevNode = head;
	boolean hasValue = false;
	Node<E> x = head;	// removedNode 
		
	// value 와 일치하는 노드를 찾는다.
	for (; x != null; x = x.next) {
		if (value.equals(x.data)) {
			hasValue = true;
			break;
		}
		prevNode = x;
	}
 
	// 일치하는 요소가 없을 경우 false 반환
	if(x == null) {
		return false;
	}
 
	// 만약 삭제하려는 노드가 head라면 기존 remove()를 사용 	
	if (x.equals(head)) {
		remove();
		return true;
	}
 
	else {
		// 이전 노드의 링크를 삭제하려는 노드의 다음 노드로 연결
		prevNode.next = x.next;
		
		x.data = null;
		x.next = null;
		size--;
		return true;
	}
}

 

1) 가장 앞의 요소(head) 삭제(삭제 연산의 기초) - remove()

https://st-lab.tistory.com/167

head가 가리키는 노드의 링크와 데이터를 null로 지워준 뒤 head를 다음 노드로 업데이트 해준다.

 

2) 특정 index의 요소 삭제 - remove(int index)

https://st-lab.tistory.com/167

삭제하려는 노드의 이전 노드의 next변수를 삭제하려는 노드의 다음 노드를 가리키게 해준다.

총 알아야 할 노드는 3개 = 삭제할 노드, 삭제할 노드의 이전 노드, 삭제할 노드의 다음 노드

 

3) 특정 요소 삭제 - remove(Object value)

https://st-lab.tistory.com/167

remove(int index)메소드와 동일한 메커니즘으로 작동한다. 하지만 삭제하려는 요소가 존재하는지를 꼭 염두해두어야한다.

삭제하려는 요소를 찾지못했을 경우 false반환, 찾았을 경우 remove(int index)와 동일한 삭제 방법을 사용한다. 

 

 

5. get, set, indexOf, contains

@Override
public E get(int index) {
	return search(index).data;
}
 
@Override
public void set(int index, E value) {
	Node<E> replaceNode = search(index);
	replaceNode.data = null;
	replaceNode.data = value;
}
 
@Override
public int indexOf(Object value) {
	int index = 0;
	for (Node<E> x = head; x != null; x = x.next) {
		if (value.equals(x.data)) {
			return index;
		}
		index++;
	}
	return -1;
}
 
@Override
public boolean contains(Object item) {
	return indexOf(item) >= 0;
}

 

1) get(int index) :노드의 데이터 반환

2) set(int index, E value) : 기존 index에 위치한 데이터를 새로운 데이터로 교환

3) indexOf(Object value) : 찾고자하는 요소의 위치(index)를 반환 (없을 경우 -1 반환)

4) contains(Object value) : 찾고자하는 요소의 존재여부 반환(true false)

 

 

6. size, isEmpty, clear

@Override
public int size() {
	return size;
}
 
@Override
public boolean isEmpty() {
	return size == 0;
}
 
@Override
public void clear() {
	for (Node<E> x = head; x != null;) {
		Node<E> nextNode = x.next;
		x.data = null;
		x.next = null;
		x = nextNode;
	}
	head = tail = null;
	size = 0;
}

 

1) size() : 요소의 개수 반환

2) isEmpty() : 요소가 비어있는지 확인

3) clear() : 모든 요소를 삭제

 

 

7. clone

SLinkedList<Integer> original = new SLinkedList<>();
original.add(10);	// original에 10추가 
 
SLinkedList<Integer> copy = original;
SLinkedList<Integer> clone = (SLinkedList<Integer>) original.clone();
 
copy.add(20);	// copy에 20추가
clone.add(30);	// clone에 30추가
 
System.out.println("original list");
for(int i = 0; i < original.size(); i++) {
	System.out.println("index " + i + " data = " + original.get(i));
}
 
System.out.println("\ncopy list");
for(int i = 0; i < copy.size(); i++) {
	System.out.println("index " + i + " data = " + copy.get(i));
}
 
System.out.println("\nclone list");
for(int i = 0; i < clone.size(); i++) {
	System.out.println("index " + i + " data = " + clone.get(i));
}
 
System.out.println("\noriginal list reference : " + original);
System.out.println("copy list reference : " + copy);
System.out.println("clone list reference : " + clone);

사용자가 사용하고 있던 LinkedList를 새로 하나 복제하고 싶을 때 쓰는 메소드

얕은 복사(shallow copy) = copy

깊은 복사 = clone

 

 

8. toArray

public Object[] toArray() {
	Object[] array = new Object[size];
	int idx = 0;
	for (Node<E> x = head; x != null; x = x.next) {
		array[idx++] = (E) x.data;
	}
	return array;
}
 
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	if (a.length < size) {
		// Array.newInstance(컴포넌트 타입, 생성할 크기) 
		a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
	}
	int i = 0;
	Object[] result = a;
	for (Node<E> x = head; x != null; x = x.next) {
		result[i++] = x.data;
	}
	return a;
}

 

1) Object[] toArray()
아무런 인자 없이 LinkedList의 객체를 객체배열(Object)로 반환해주는 메소드

LinkedList에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환되는 장점이 있다.

 

2) T[] toArray(T[] a)

이미 생성된 다른 배열에 LinkedList를 복사해주는 메소드

SLinkedList<Integer> list = new SLinkedList<>();
 
// get list to array (using toArray())
Object[] array1 = list.toArray();
 
// get list to array (using toArray(T[] a)
Integer[] array2 = new Integer[10];
array2 = list.toArray(array2);

ArrayList와의 배열 생성방식에 차이가 있는데, ArrayList에서는 내부에서 데이터를 Object[] 배열에 담았기때문에 데이터 복사가 쉬웠으나,

LinkedList는 노드라는 객체에 데이터를 담고 있는 연결리스트이기때문에 노드 자체가 Integer, String처럼 래퍼클래스나 사용자정의 데이터를 가질 수 없다.

노드의 data변수가 객체 타입 변수인 것이지 노드 자체가 객체 타입을 갖지는 못한다. 

그래서 ArrayList처럼 Arrays.copyOf() 메소드나 System.arraycopy를 쓰기 어렵다.

 

이럴때 쓰는 것이 lang.reflect 패키지에 있는 Array클래스의 newInstance 메소드이다.

 

예를 들어 E Type이 Integer이고, T Type이 Object라고 가정해볼때

Object는 Integer보다 상위 타입으로 Object안에 Integer타입의 데이터를 담을 수 있다.

상위 타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성한 것이다.

하위 타입(축소)의 경우 Array클래스에서 예외를 던지기 때문에 이에 대한 별다른 예외를 처리할 필요는 없다.

 

<파라미터로 주어지는 배열 A가 현재 리스트의 요소보다 작은 경우>

파라미터로 주어지는 배열 A의 타입을 알기 위해 getClass().getComponentType()을 통해 객체가 어떤 유형의 배열인지를 판단하고 배열의 크기를 설정한다.

그런 다음 A를 얕은 복사를 통해 Object[] 배열을 하나 만들어 데이터를 넣어준다음 A를 반환한다.

얕은 복사이기 때문에 result 배열에 담으면 자동으로 A배열에도 영향을 미치는 것을 활용한 방법이다.

 

<파라미터로 주어지는 배열 A가 현재 리스트의 요소보다 큰 경우>

앞부분부터 array에 있던 요소만 복사해서 A배열에 넣고 반환한다.

 

 

9. sort

// Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법

import java.util.Comparator;
public class test {
	public static void main(String[] args) {
		SLinkedList<Student> list = new SLinkedList<>();
 
		list.add(new Student("김자바", 92));
		list.add(new Student("이시플", 72));
		list.add(new Student("조시샵", 98));
		list.add(new Student("파이손", 51));
 
		list.sort(customComp);	// Comparator을 파라미터로 넘겨준다.
        
		for(int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
	}
	// 사용자 설정 comparator(비교기)
	static Comparator<Student> customComp = new Comparator<Student>() {
		@Override
		public int compare(Student o1, Student o2) {
			return o2.score - o1.score;
		}
	};
 
}
 
class Student {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
}

 

// Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법

public class test {
	public static void main(String[] args) {
		SLinkedList<Student> list = new SLinkedList<>();
 
		list.add(new Student("김자바", 92));
		list.add(new Student("이시플", 72));
		list.add(new Student("조시샵", 98));
		list.add(new Student("파이손", 51));
 
		list.sort();
		for(int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
	}
}
 
class Student implements Comparable<Student> {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
 
	@Override
	public int compareTo(Student o) {
		return o.score - this.score;
	}
}

ArrayList에서는 내부적으로 Object[] 배열을 사용하기 때문에 Arrays.sort() 메소드를 쓰면 간단하다.

하지만 LinkedList같은 객체 배열의 경우 Collections.sort() 메소드를 사용하게 되는데, 해당 메소드도 내부에서는 Arrays.sort()를 쓴다.

리스트를 Object[] 배열로 반환시켜 Arrays.sort()를 통해 정렬한 후 정렬된 데이터를 다시 리스트의 노드에서 셋팅해준다.

 

래퍼클래스 타입이라면 따로 Comparator를 구현해주지 않아도 되지만, 사용자 정의 클래스같은 경우에는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 Comparator를 구현해서 파라미터로 넘겨줘야한다.

정렬 메소드를 생성할 때 Comparable이 구현되어있는 파라미터로 Comparator를 넘겨주지않는 경우와 Comparator를 넘겨주어 정의된 정렬 방식을 사용하는 경우를 생각해야한다.

 

 

Collections.sort() - Comparator 파라미터가 없는 경우

출처 : https://st-lab.tistory.com/167

 

Collections.sort() - Comparator 파라미터가 있는 경우

출처 : https://st-lab.tistory.com/167

 

List.sort() - List 인터페이스의 default메소드

출처 : https://st-lab.tistory.com/167

 


출처 및 참고

https://st-lab.tistory.com/167

https://prinha.tistory.com/entry/JAVA-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ArrayList

 

[JAVA 자료구조] ArrayList

ArrayList Object[] 객체 배열을 사용하는 자료구조로 사이즈를 정하지 않고 동적으로 활용할 수 있다. 리스트 계열 자료구조는 데이터 사이에 빈 공간을 허락하지 않는다. 더보기 package Interface_form; /

prinha.tistory.com

 

728x90
반응형