Objectives
Today i'm going to introduce you in my custom LinkedList implementation.Below is prepared diagram which shows internal class's structure. Every Node handles reference to next Node. The last Node has an empty reference. There are two fields which hold reference to first and last Nodes.
private class Node<T extends Object>{
Node<T> next;
T object;
public Node(T object){
this.next = null;
this.object = object;
}
public Node(T object, Node<T> next){
next.setNext(this);
this.next = null;
this.object = object;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
public T getObject() {
return object;
}
public void setObject(T object) {
this.object = object;
}
}
Inserting new Items
There are two methods to inset new item:- add(T) - find reference to last Node using "last" field in internal class's structure and add next Node and set reference. "last" field should be changed.
- add(int i, T) - this operation takes usually mach more time because algorithm has to find "head" field and iterate over Nodes to find Node with index "i". After that method inserting new Node and set appropriate references.
Removing Items
There is only one method to remove items: remove(int i). This method is similar to add(int i, T) because algorithm has to find "head" field and iterate over Nodes to find Node with index "i" and then remove selected Node and set references.Reverting LinkedList
There is created method to revet list. This method is simple - algorithm iterate over all Nodes and each Node is inserted always as first item.public MyLinkedList<T> revert(){
MyLinkedList<T> revertList = new MyLinkedList<T>();
Node<T> currentNode = head;
if(head != null){
for(int idx = 0; idx < this.getSize(); idx ++){
revertList.add(0, currentNode.getObject());
currentNode = currentNode.getNext();
}
}
return revertList;
}
Main Class
package artsci.pl;
/**
*
* @author Artur
*/
public class MyLinkedList<T extends Object> {
private Node<T> head;
private Node<T> last;
private int counter = 0;
public void add(T t){
if(head == null){
head = new Node<T>(t);
last = head;
counter++;
return;
}
last = new Node<T>(t, last);
counter++;
}
public void add(int i, T t) {
if(head == null){
add(t);
return;
}
Node<T> previousNode = null;
Node<T> currentNode = head;
Node<T> tmpNode = new Node<T>(t);
//int idx = 0;
if(i >= 0 && (counter) >= i && currentNode != null){
for(int j = 0; j <= counter; j++){
if(j == i){
if(previousNode == null){
tmpNode.setNext(currentNode);
head = tmpNode;
}else{
previousNode.setNext(tmpNode);
tmpNode.setNext(currentNode);
}
if(currentNode == null){
last = currentNode;
}
counter++;
break;
}else{
previousNode = currentNode;
currentNode = currentNode.getNext();
}
}
}
}
public void remove(int i) {
Node<T> previousNode = null;
Node<T> currentNode = head;
if(i >= 0 && (counter) >= i && currentNode != null){
for(int j = 0; j <= counter; j++){
if(j == i){
if(previousNode == null){
head = currentNode.getNext();
}else{
previousNode.setNext(currentNode.getNext());
}
if(currentNode.getNext() == null){
last = previousNode;
}
counter--;
break;
}
previousNode = currentNode;
currentNode = currentNode.getNext();
}
}
}
public T get(int i){
Node<T> currentNode = head;
if(i >= 0 && (counter) >= i && head != null){
for(int idx = 0; idx < i; idx ++){
currentNode = currentNode.getNext();
}
if(currentNode != null){
return currentNode.getObject() != null ? currentNode.getObject() : null;
}else{
return null;
}
}else{
return null;
}
}
public MyLinkedList<T> revert(){
MyLinkedList<T> revertList = new MyLinkedList<T>();
Node<T> currentNode = head;
if(head != null){
for(int idx = 0; idx < this.getSize(); idx ++){
revertList.add(0, currentNode.getObject());
currentNode = currentNode.getNext();
}
}
return revertList;
}
public String toString() {
Node<T> currentNode = head;
String out = "[";
while (currentNode != null && currentNode.getObject() != null) {
out += currentNode.getObject().toString().concat(";");
currentNode = currentNode.getNext();
}
return out.concat("]");
}
public int getSize(){
return getCounter();
}
public int getCounter() {
return counter;
}
private class Node<T extends Object>{
Node<T> next;
T object;
public Node(T object){
this.next = null;
this.object = object;
}
public Node(T object, Node<T> next){
next.setNext(this);
this.next = null;
this.object = object;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
public T getObject() {
return object;
}
public void setObject(T object) {
this.object = object;
}
}
}
Test Class
package artsci.pl;
/**
*
* @author Artur
*/
public class ListTester {
public static void main(String[] args) {
MyLinkedList<Integer> myList = new MyLinkedList<Integer>();
System.out.println("-- Main test --");
for(int i = 0; i <10; i++){
myList.add(i);
myList.add(0,i);
}
myList.remove(9);
myList.remove(9);
System.out.println("myList -> " + myList.toString());
System.out.println("-- Revert list --");
/* Revert list */
MyLinkedList<String> basicList = new MyLinkedList<String>();
basicList.add("Jane");
basicList.add("Tom");
basicList.add("Tim");
System.out.println("basicList -> "+ basicList.toString());
MyLinkedList<String> revertList = basicList.revert();
System.out.println("revertList -> "+ revertList.toString());
}
}
And the result is below:
run:
-- Main test --
myList -> [9;8;7;6;5;4;3;2;1;1;2;3;4;5;6;7;8;9;]
-- Revert list --
basicList -> [Jane;Tom;Tim;]
revertList -> [Tim;Tom;Jane;]
BUILD SUCCESSFUL (total time: 0 seconds)
No comments:
Post a Comment