欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2019.10.19双向链表

程序员文章站 2022-05-09 16:09:56
import java.util.NoSuchElementException;public class LinkedListT { private Node first; private Node last; long size = 0l; private void linkLa ......

import java.util.nosuchelementexception;

public class linkedlistt<e> {
private node<e> first;

private node<e> last;

long size = 0l;

private void linklast(e e) {
node<e> temp = last;
node<e> newnode = new node<e>(temp, e, null);
last = newnode;
if (temp == null) {
first = newnode;
} else {
temp.next = newnode;
}
size++;
}

public boolean add(e e) {
linklast(e);
return true;
}

public boolean add(long index, e e) {
checkinsertindex(index);
if (index > 0 && index < size) {
//从前到后的查法
/*long j = 0;
for (node<e> i = first; i != null; i = i.next, j++) {
if (j == index) {
node<e> newnode = new node<>(i.prev, e, i);
i.prev.next = newnode;
i.prev = newnode;
}
}*/
//分前后查找法
node<e> node = indexnode(issize(index), index);
node<e> newnode = new node<>(node.prev, e, node);
node.prev.next = newnode;
node.prev = newnode;
size++;
} else if (index == 0) {
addfirst(e);
}
if (index == size) {
linklast(e);
}
return true;
}

public void checkinsertindex(long index) {
if (index > size || index < 0) {
throw new indexoutofboundsexception();
}
}

public boolean addfirst(e e) {
if (size == 0) {
linklast(e);
} else {
node<e> newnode = new node<>(null, e, first);
first.prev = newnode;
first = newnode;
size++;
}
return true;
}

public boolean addlast(e e) {
linklast(e);
return true;
}

public e getfirst() {
if (first == null) {
throw new nosuchelementexception();
}
return first.item;
}

public e getlast() {
if (last == null) {
throw new nosuchelementexception();
}
return last.item;
}

public long getsize() {
return size;
}

public e get(long index) {
e result = null;
checkinsertindex(index);
long j = 0;
for (node<e> i = first; i != null; i = i.next, j++) {
if (j == index) {
result = i.item;
}
}
return result;
}

public void removeall() {
first = null;
last = null;
size = 0;
}

public e remove(long index) {
e e = null;
checkremoveindex(index);
if (index != 0 && index != size - 1){
node<e> node = indexnode(issize(index), index);
// node<e> prev = node.prev;
node.prev.next = node.next;
node.next.prev = node.prev;
e = node.item;
node = null;
size--;
}else if(index == 0){
e = removefirst();
}else {
e = removelast();
}
return e;
}

private void checkremoveindex(long index){
if (index >= size || index < 0) {
throw new indexoutofboundsexception();
}
}

private node<e> indexnode(boolean flag, long index) {
long j = 0;
node<e> node = null;
if (flag) {
for (node<e> i = first; i != null; i = i.next, j++) {
if (index == j) {
node = i;
}
}
} else {
j = size - 1;
for (node<e> i = last; i != null; i = i.prev, j--) {
if (index == j){
node = i;
}
}
}
return node;
}

private boolean issize(long index) {
if (size / 2 >= index) {
return true;
} else {
return false;
}
}

public e remove(object obj) {
e e = null;
if (obj == null){
for ( node<e> i = first;i != null;i = i.next){
if (i.item == obj){
e = unlink(i);
}
}
}else {
for ( node<e> i = first;i != null;i = i.next){
if (i.item.equals(obj)){
e = unlink(i);
}
}
}
return e;
}

e unlink(node<e> x) {
e element = x.item;
node<e> next = x.next;
node<e> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
return element;
}

public e removefirst() {
if (size == 0) {
throw new indexoutofboundsexception();
}
node<e> second = first.next;
e e = first.item;
first.next = null;
if (second == null) {
last = null;
} else {
second.prev = null;
}
first = second;
size--;
return e;
}

public e removelast() {
if (size == 0) {
throw new indexoutofboundsexception();
}
node<e> secondlast = last.prev;
e e = last.item;
last.prev = null;
if (secondlast == null) {
first = null;
} else {
secondlast.next = null;
}
last = secondlast;
size--;
return e;
}

private static class node<e> {
e item;
node<e> next;
node<e> prev;

node(node<e> prev, e item, node<e> next) {
this.item = item;
this.next = next;
this.prev = prev;
}
}

@override
public string tostring() {
stringbuffer str = new stringbuffer("");
for (node<e> i = first; i != null; i = i.next) {
str.append(i.item);
if (i.next != null) {
str.append(",");
}
}
return "[" + str.tostring() + "]";
}
}