728x90
⬛ LinkedList 개념
- 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조로 다음 노드에 대한 참조를 통해 연결된다.
- 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다.
- 동적으로 메모리를 사용할 수 있기 때문에 메모리를 효율적으로 사용할 수 있다.
- 삭제와 삽입의 과정만은 O(1)으로 해결되지만 해당 위치를 찾기 위해 첫 번째 노드부터 순차적으로 요소에 접근하는 과정에서 O(n)의 시간이 추가적으로 발생한다. 결국 O(n)의 시간복잡도를 가지게 된다.
⬛ LinkedList 연산
1. add(E e) : list의 끝에 지정된 요소를 추가
2. add(int index, E element) : list의 지정된 위치에 지정된 요소 삽입
3. addFirst(E e) : list의 시작 부분에 지정된 요소 삽입
4. get(int index) : list의 지정된 위치에 있는 요소를 반환
5. remove(int index) : list의 지정된 위치에 있는 요소를 제거
6. set(int index, E element) : list의 지정된 위치에 있는 요소를 지정된 요소로 바꾸기
7. clear() : list의 모든 요소를 제거
8. size() : list의 요소 수를 반환
⬛ LinkedList 구현
MyLinkedList.java
더보기
MyLinkedList.java
package com.LinkedList;
public class MyLinkedList{
private Node head = new Node();
private Node tail;
private int size = 0;
// Appends the specified element to the end of this list.
private void add(int data){
if (size == 0) {
Node new_node = new Node(data);
head.next = new_node;
tail = new_node;
size++;
return;
}
Node new_node = new Node(data);
tail.next = new_node;
tail = new_node;
size++;
}
// Inserts the specified element at the specified position in this list.
private void add(int index, int data){
if (index == 0) {
addFirst(data);
return;
}
Node new_node = new Node(data);
Node pre_node = node(index - 1);
new_node.next = pre_node.next;
pre_node.next = new_node;
size++;
}
// Inserts the specified element at the beginning of this list.
private void addFirst(int data){
Node new_node = new Node(data);
new_node.next = head.next;
head.next = new_node;
size++;
}
private Node node(int index){
Node search = head;
for (int i = 0; i <= index; i++) {
search = search.next;
}
return search;
}
// returns the element at the specified position in this list.
private int get(int index){
return node(index).data;
}
// Removes the element at the specified position in this list.
private void remove(int index){
Node pre_node = node(index - 1);
Node cur_node = node(index);
Node next_node;
if (index == size - 1) {
tail = pre_node;
pre_node = node(index - 1);
pre_node.next = null;
size--;
return;
}
next_node = node(index + 1);
pre_node.next = next_node;
cur_node = null;
size--;
}
// Replaces the element at the specified position in this list with the specified elements.
private void set(int index, int data){
node(index).data = data;
}
// Removes all of the elements from this list.
private void clear(){
int curSize = size();
for (int i = 0; i < curSize; i++) {
remove(0);
}
}
// returns the number of elements in this list.
private int size(){
return size;
}
@Override
public String toString(){
if (size == 0) {
return "[]";
}
String str = "[";
Node search = head.next;
while (search.next != null) {
str += search.data + ", ";
search = search.next;
}
str += search.data + "]";
return str;
}
public static void main(String[] args){
MyLinkedList list = new MyLinkedList();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
list.add(1, 5);
System.out.println(list);
list.addFirst(6);
System.out.println(list);
list.remove(0);
System.out.println(list);
list.set(3, 9);
System.out.println(list);
System.out.println(list.get(2));
System.out.println(list.size());
list.clear();
System.out.println(list);
}
}
Node.java
더보기
Node.java
package com.LinkedList;
public class Node {
int data;
Node next;
Node(int data){
this.data = data;
}
Node(){
}
}
728x90
'공부의 기록 > Data Structure' 카테고리의 다른 글
[자료 구조] Tree & Binary Tree의 개념 설명 (0) | 2022.03.02 |
---|---|
[자료 구조] Hash의 개념 설명 (0) | 2022.02.11 |
[자료 구조] Heap의 개념 설명과 구현 (0) | 2022.02.03 |
[자료 구조] Queue 개념 설명과 구현 (0) | 2022.02.02 |
[자료 구조] Stack 개념 설명과 구현(배열, 연결리스트) (0) | 2022.01.31 |