JDK中的LinkedList属于双向循环链表.
下面是使用Java来实现一个双向非循环链表.
package org.cgz.practice2; import java.util.NoSuchElementException; /** * 双向非循环链表 * @author cgz * @param <E> */ public class MyLinkedList<E> { /** * 定义一个结点类 * @author cgz * @param <E> */ private static class Node<E> { private Node<E> prev; private Node<E> next; private E data; public Node(E data, Node<E> prev, Node<E> next) { this.data = data; this.prev = prev; this.next = next; } } private Node<E> head; private Node<E> tail; private transient int size = 0; public MyLinkedList() { head = tail = null; } /** ------------------添加------------------ **/ public void add(E e) { addLast(e); } /** * 在index处插入一个元素 * * @param index * @param e */ public void add(int index, E e) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("index:" + index + ",size:"+ size); } if (head == null) { // 当链表为空时,添加一个新结点 head = new Node<E>(e, null, null); tail = head; } else { if (index == 0) { // 在链表头部插入元素 Node<E> newNode = new Node<E>(e, null, head); head.prev = newNode; head = newNode; } else if (index == size) { // 在链表尾部插入 Node<E> newNode = new Node<E>(e, tail, null); tail.next = newNode; tail = newNode; } else { Node<E> newNode = new Node<E>(e, null, null); Node<E> current = getNodeByIndex(index); current.prev.next = newNode; newNode.prev = current.prev; current.prev = newNode; newNode.next = current; } } size++; } /** * 在链表头添加元素 * * @param e */ public void addFirst(E e) { add(0, e); } /** * 在链表末尾添加元素 * * @param e */ public void addLast(E e) { add(size, e); } /** * 根据index获取所在位置的元素 * @param index * @return */ private Node<E> getNodeByIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("index:" + index + ",size:"+ size); } if(size==0) { throw new NoSuchElementException(); } Node<E> current; // 如果index在链表前半段,则从表头开始查找 if (index <= size / 2) { current = head; for (int i = 1; i <= index; i++) { current = current.next; } } else { // 如果index在链表后半段,则从尾部查找 current = tail; for (int i = size-1; i >= index+1; i--) { current = current.prev; } } return current; } /** ------------------删除------------------ **/ public boolean remove(E e) { int index = indexOf(e); if(index!=-1) { remove(index); return true; } return false; } /** * 根据index删除元素 * @param index * @return */ public E remove(int index) { Node<E> node = getNodeByIndex(index); E old = null; //删除链表头 if (index == 0) { old = head.data; head.next.prev = null; head = head.next; //删除链表尾 } else if (index == size-1) { old = tail.data; tail.prev.next = null; tail = tail.prev; } else { old = node.data; node.prev.next = node.next; node.next.prev = node.prev; } size--; return old; } /** * 删除首元素 * @return */ public E removeFirst() { return remove(0); } /** * 删除尾元素 * @return */ public E removeLast() { return remove(size-1); } /** * 清空链表 */ public void clear() { Node<E> current = head; while(current!=null) { Node<E> next = current.next; current.prev = current.next = null; current.data = null; current = next; } size = 0; } /** ------------------修改------------------ **/ public E set(int index, E e) { Node<E> oldNode = getNodeByIndex(index); E oldData = oldNode.data; oldNode.data = e; return oldData; } /** ------------------查询------------------ **/ /** * 返回index处的元素 * @param index * @return */ public E get(int index) { return getNodeByIndex(index).data; } /** * 返回首元素 * @return */ public E getFirst() { return get(0); } /** * 返回最后一个元素 * @return */ public E getLast() { return get(size-1); } /** * 返回元素在链表中的位置 * @param e * @return */ public int indexOf(E e) { Node<E> current = head; int count = 0; while(current!=null) { if(current.data.equals(e)) { return count; } current = current.next; count++; } return -1; } /** * 是否包含元素e * @param e * @return */ public boolean contains(E e) { return indexOf(e)!=-1; } /** * 链表是否为空 * @return */ public boolean isEmpty() { return size == 0; } /** * 链表长度 * @return */ public int size() { return size; } /** * 输出链表中的所有元素 */ public void print() { System.out.print(this.getClass().getSimpleName() + ":["); Node<E> current = head; while(current!=null) { System.out.print(current.data + " "); current = current.next; } System.out.print("]"); } }
相关推荐
javalist数据结构_Java数据结构-------List 三种List:ArrayList,Vector,LinkedList 类继承关系图 ArrayList和Vector通过数组实现,⼏乎使⽤了相同的算法;区别是ArrayList不是线程安全的,Vector绝⼤多数⽅法做了...
约瑟夫环 leetcode ...LinkedList双向链表实现解决约瑟夫环问题 04-栈 Stack利用java组合实现栈 05-队列 Queue队列实现 Deque双端队列实现 CircleQueue环形队列实现 CircleDeque环形双端队列实现 06-二叉树
数据结构:双向链表 Vector: 数据结构:一维数组 Stack: 数据结构:一维数组 特点:模拟了栈的模式 Set -- Set接口(没有对下标操作的方法) 特点:无序的,且不可重复 HashSet: 数据...
【链表List】单向链表 SingleLinkedList、双向链表 LinkedList 实现源码 【循环链表CircleList】单向循环链表、双向循环链表以及约瑟夫环问题 【队列Queue】队列 Queue、双端队列 DeQueue、循环队列 CircleQueue、...
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。 链表可分为单向链表和双向链表。 一个单向链表包含两个值: 当前节点的值...
剖析⾯试最常⻅问题之 Java 集合框架 集合概述 Java 集合概览 从下图可以看出,在 Java 中除了以 ...LinkedList : 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环) Set HashSet (⽆序,唯⼀): 基于 HashMap 实
答:①ArrayList和LinkedList可想从名字分析,它们一个是Array(动态数组)的数据结构,一个是Link(链表)的数据结构,此外,它们两个都是对List接口的实现。 前者是数组队列,相当于动态数组;后者为双向链表结构,也...
数据结构,如何遍历List中的元素? 如果要按照键值保存或者访问数据,使用什么数据结构? 要掌握Collection相关的接口和类的使用 56.使用StringBuffer类与String类进行字符串连接时有何区别? 57.调用Thread类的...
通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。 8、EJB是基于哪些技术实现的?并说出Session...
通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。 11、EJB是基于哪些技术实现的?并说出...
通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。 8、EJB是基于哪些技术实现的?并说出Session...
9.3.3 双向链表 9.4 线性表的分析 9.4.1 线性表的实现分析 9.4.2 线性表的功能 9.5 小结 第10课 栈和队列 10.1 栈 10.1.1 栈的基本定义 10.1.2 栈的常用操作 10.1.3 栈的顺序存储结构及实现 10.1.4 栈的...
通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。 8、EJB是基于哪些技术实现的?并说出Session...