双链表 LinkedList
实现代码
package com.lhs;
public class LinkedList<E> implements List<E>{
// 定义链表长度
private int size;
// 定义头节点
private Node<E> first;
// 定义尾节点
private Node<E> last;
// 内部类,定义节点
public static class Node<E>{
// 定义节点数据
E data;
// 定义下一个节点
Node<E> next;
// 定义前一个节点
Node<E> pre;
// 构造函数,用于创建新的节点
Node(E data,Node<E> next,Node<E> pre){
this.data = data;
this.next = next;
this.pre = pre;
}
}
// 重写size方法,返回链表长度
@Override
public int size() {
return size;
}
// 重写isEmpty方法,判断链表是否为空
@Override
public boolean isEmpty() {
return size == 0;
}
// 重写contains方法,判断链表是否包含某元素
@Override
public boolean contains(Object o) {
return IndexOf(o) >= 0;
}
// 重写IndexOf方法,返回某元素在链表中的位置
public int IndexOf(Object o){
Node<E> node = first;
if (o == null){
for (int i = 0; i < size; i++) {
if (node.data == null){
return i;
}
node = node.next;
}
return -1;
}else{
for (int i = 0; i < size; i++) {
if (o.equals(node.data)){
return i;
}
node = node.next;
}
return -1;
}
}
// 重写add方法,向链表末尾添加元素
@Override
public boolean add(E e) {
if (size == 0){
Node<E> node = new Node<>(e, null, null);
first = node;
last = node;
}else{
Node<E> l = last;
Node<E> node = new Node<>(e, null, l);
l.next = node;
last = node;
}
size++;
return true;
}
// 重写get方法,返回链表中指定位置的元素
@Override
public E get(int index) {
if(index >= size){
throw new IndexOutOfBoundsException(index + " out of bound");
}
Node<E> node;
if(index > (size >> 1)){
node = last;
for(int i = 0 ; i<size - index - 1;i++){
node = node.pre;
}
}else{
node = first;
for (int i = 0; i < size - index - 1; i++) {
node = node.next;
}
}
return node.data;
}
// 重写set方法,替换链表中指定位置的元素
@Override
public E set(int index, E e) {
if(index >= size){
throw new IndexOutOfBoundsException(index + " out of bound");
}
E oldVal;
Node<E> node;
if(index > (size >> 1)){
node = last;
for(int i = 0 ; i<size - index - 1;i++){
node = node.pre;
}
}else{
node = first;
for (int i = 0; i < size - index - 1; i++) {
node = node.next;
}
}
oldVal = node.data;
node .data = e;
return oldVal;
}
// 重写remove方法,移除链表中指定位置的元素
@Override
public E remove(int index) {
if(index >= size){
throw new IndexOutOfBoundsException(index + " out of bound");
}
Node<E> node;
if(index > (size >> 1)){
node = last;
for(int i = 0 ; i<size - index - 1;i++){
node = node.pre;
}
}else{
node = first;
for (int i = 0; i < size - index - 1; i++) {
node = node.next;
}
}
E oldVal = node.data;
Node<E> n = node.next;
Node<E> p = node.pre;
if(p != null){
p.next = n;
}else{
first = n;
}
if(n != null){
n.pre = p;
}else{
last = p;
}
size--;
return oldVal;
}
// 重写addFirst方法,向链表头部添加元素
@Override
public void addFirst(E e) {
Node<E> f = first;
Node<E> node = new Node<>(e, null, f);
f.pre = node;
first = node;
size++;
}
// 重写addLast方法,向链表尾部添加元素
@Override
public void addLast(E e) {
add(e);
}
// 重写removeFirst方法,移除链表头部元素
@Override
public E removeFirst() {
return remove(0);
}
// 重写removeLast方法,移除链表尾部元素
@Override
public E removeLast() {
return remove(size-1);
}
}
测试代码
/**
* Welcome to https://waylau.com
*/
package com.lhs;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import static junit.framework.TestCase.*;
import static org.junit.Assert.assertThrows;
/**
* LinkedList Test.
*
* @since 1.0.0 2020年5月4日
* @author <a href="https://waylau.com">Way Lau</a>
*/
public class LinkedListTests {
@Test
public void testSize() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
assertTrue(list.size() == 0);
list.add("Java");
assertTrue(list.size() == 1);
}
@Test
public void testIsEmpty() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
assertTrue(list.isEmpty());
list.add("Java");
assertFalse(list.isEmpty());
}
@Test
public void testContains() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
list.add("Python");
list.add("TypeScript");
// 判断存在
assertTrue(list.contains("Java"));
// 判断不存在
assertFalse(list.contains("Java++"));
}
@Test
public void testAdd() {
// 实例化LinkedList
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
assertFalse(list.isEmpty());
}
@Test
public void testGet() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
// 判断存在
assertEquals("C++", list.get(1));
// 判断不存在
int index = 6;
Throwable excpetion = assertThrows(
IndexOutOfBoundsException.class, () -> {
list.get(index);// 抛异常
});
assertNotNull(excpetion.getMessage());
}
@Test
public void testSet() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
// 判断存在
assertEquals("C", list.set(2, "Python"));
// 判断不存在
int index = 6;
Throwable excpetion = assertThrows(
IndexOutOfBoundsException.class, () -> {
list.set(index, "Python");// 抛异常
});
assertNotNull(excpetion.getMessage());
}
@Test
public void testRemove() {
// 实例化LinkedList
List<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
// 判断存在
assertEquals("C", list.remove(2));
assertEquals("C++", list.remove(1));
assertEquals("Java", list.get(0));
// 判断不存在
int index = 6;
Throwable excpetion = assertThrows(
IndexOutOfBoundsException.class, () -> {
list.remove(index); // 抛异常
});
assertNotNull(excpetion.getMessage());
}
@Test
public void testAddFirst() {
// 实例化LinkedList
LinkedList<String> list = new LinkedList<String>();
list.addFirst("Java");
list.addFirst("C++");
list.addFirst("C");
// 判断存在
assertEquals("C", list.get(0));
assertEquals("C++", list.get(1));
assertEquals("Java", list.get(2));
}
@Test
public void testAddLast() {
// 实例化LinkedList
LinkedList<String> list = new LinkedList<String>();
list.addLast("Java");
list.addLast("C++");
list.addLast("C");
// 判断存在
assertEquals("Java", list.get(0));
assertEquals("C++", list.get(1));
assertEquals("C", list.get(2));
}
@Test
public void testRemoveFirst() {
// 实例化LinkedList
LinkedList<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
// 判断存在
assertEquals("Java", list.removeFirst());
assertEquals("C++", list.removeFirst());
assertEquals("C", list.removeFirst());
}
@Test
public void testRemoveLast() {
// 实例化LinkedList
LinkedList<String> list = new LinkedList<String>();
list.add("Java");
list.add("C++");
list.add("C");
// 判断存在
assertEquals("C", list.removeLast());
assertEquals("C++", list.removeLast());
assertEquals("Java", list.removeLast());
}
}
文章来源地址https://www.toymoban.com/news/detail-806702.html
文章来源:https://www.toymoban.com/news/detail-806702.html
到了这里,关于java数据结构与算法:双链表 LinkedList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!