一、基本操作
LinkedList基于双链表实现。
- 链表无容量限制，但双链表本身占用空间
- 按下标访问元素需要遍历一半链表移动到位
-
插入、删除时：还是要遍历部分链表才能移动到链表所指向的位置
二、常用API
三、实现了上述基本操作的LinkedList
增
1，按照普适思路编写；2，注意判空
/**
* 插入单个节点
* 从双链表的尾部插入
* @param e
* @return
*/
public boolean add(E e){
linkLast(e);
return true;
}
/**
* 将节点连接到双链表尾部
* @param e
*/
private void linkLast(E e){
Node<E> l=last;
// 新节点指向前一节点
Node<E> newNode=new Node<E>(l,e,null);
// 更改last指针
last=newNode;
// 原来的last节点指向新节点（需考虑原来的last节点为null的情况）
if(l==null){
first=newNode;
}else{
l.next=newNode;
}
// size++
size++;
}
/**
* 从index
* @param index
* @param e
* @return
*/
public void add(int index, E e){
// index要在[0,size]的闭区间内
if(index==size){
// 插入到链表尾部
linkLast(e);
}else{
// 将新节点插入到"第index节点"之前
linkBefore(e,node(index));
}
}
删
1，按照普适思路编写；2，注意判空
/**
* 删除指定索引处的元素，并将删除的元素值返回
* @param index
* @return
*/
public E remove(int index){
checkElementIndex(index);
return unlink(node(index));
}
/**
* 删除指定元素
* 需要遍历链表
* @param o
* @return
*/
public boolean remove(Object o){
if(o==null){
Node<E> f=first;
while(f!=null){
// 遍历链表
if(f.item==null){
unlink(f);
return true;
}
f=f.next;
}
}else{
Node<E> f=first;
while(f!=null){
// 遍历链表
if(o.equals(f.item)){
unlink(f);
return true;
}
f=f.next;
}
}
return false;
}
改
注意其中找出第index节点的方法
/**
* 修改
* @param index
* @param element
* @return
*/
public E set(int index,E element){
// index在[0,size-1]范围内则合法，否则抛出IndexOutOfBoundException
checkElementIndex(index);
Node<E> x=node(index);
E oldVal=x.item;
x.item=element;
return oldVal;
}
/**
* 找到索引为index的Node节点
* @param index
* @return
*/
private Node<E> node(int index) {
if(index<(size>>1)){
// 从first节点开始遍历
Node<E> x=first;
for(int i=0;i<index;i++){
x=x.next;
}
return x;
}else{
Node<E> x=last;
for(int i=size-1;i>index;i--){
x=x.prev;
}
return x;
}
}
4. 查
/**
* 查：得到索引处的值
* @param index
* @return
*/
public E get(int index){
checkElementIndex(index);
return node(index).item;
}
源码
import java.util.Collection;
/**
* 仿源码，自定义LinkedList
* <p>Description: </p>
* @author 杨丽金
* @date 2018-9-4
* @version 1.0
*/
public class MyLinkedList<E> {
static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.item = element;
this.next = next;
}
}
int size;// 元素个数（元素索引从0开始）
Node<E> first;// 首元素
Node<E> last;// 尾元素
// 构造函数
public MyLinkedList(){}
public MyLinkedList(Collection<? extends E> c){
this();
addAll(c);
}
/**
* 插入单个节点
* 从双链表的尾部插入
* @param e
* @return
*/
public boolean add(E e){
linkLast(e);
return true;
}
/**
* 将节点连接到双链表尾部
* @param e
*/
private void linkLast(E e){
Node<E> l=last;
// 新节点指向前一节点
Node<E> newNode=new Node<E>(l,e,null);
// 更改last指针
last=newNode;
// 原来的last节点指向新节点（需考虑原来的last节点为null的情况）
if(l==null){
first=newNode;
}else{
l.next=newNode;
}
// size++
size++;
}
/**
* 将节点连接到双链表首部
* @param e
*/
private void LinkFirst(E e){
Node<E> f=first;
// 新节点指向原来的first节点
Node<E> newNode=new Node<E>(null,e,f);
// first指针指向新节点
first=newNode;
// 原来的first节点指向新节点
if(f==null){
last=newNode;
}else{
f.prev=newNode;
}
size++;
}
/**
* 从index
* @param index
* @param e
* @return
*/
public void add(int index, E e){
// index要在[0,size]的闭区间内
if(index==size){
// 插入到链表尾部
linkLast(e);
}else{
// 将新节点插入到"第index节点"之前
linkBefore(e,node(index));
}
}
/**
* 将e插入到node之前
* @param e
* @param node
*/
private void linkBefore(E e, Node<E> succ) {
// succ的前一节点
Node<E> p=succ.prev;
Node<E> newNode=new Node<E>(p,e,succ);
// succ的prev指向newNode
succ.prev=newNode;
// p的next指向newNode（但考虑p为null的情况）
if(p==null){
first=newNode;
}else{
p.next=newNode;
}
size++;
}
public boolean addAll(Collection<? extends E> c){
return addAll(size,c);
}
/**
* 批量插入数组：
* for循环遍历数组，依次插入
* @param index
* @param c
* @return
*/
public boolean addAll(int index,Collection<? extends E> c){
// index要在[0,size]的闭区间内
// 转化成数组
Object[] a=c.toArray();
int newNum=a.length;
if(newNum==0){
// 搞笑的！都没有数据还有必要往里面插入吗？！
return false;
}
// 那么遍历c，依次插入各个元素
// 在遍历之前要准备好pred,succ（要插入范围的开始节点、结束节点）
Node<E> pred,succ;
if(index==size){
// 插入到尾部
pred=last;
succ=null;
}else{
// 插入到中间某一位置
succ=node(index);
pred=succ.prev;
}
// 遍历集合，将元素依次插入
for(Object o:a){
// 强转
@SuppressWarnings("unchecked")E e=(E)o;
Node<E> newNode=new Node<E>(pred,e,null);
if(pred==null){
// 要考虑pred为空的情况
first=newNode;
}else{
pred.next=newNode;
}
// 变量的改变
pred=newNode;
}
// 遍历完后，将succ节点连接到链表上
pred.next=succ;
if(succ==null){
last=pred;
}else{
succ.prev=pred;
}
size+=newNum;
return true;
}
/**
* 删除指定索引处的元素，并将删除的元素值返回
* @param index
* @return
*/
public E remove(int index){
checkElementIndex(index);
return unlink(node(index));
}
/**
* 删除一个节点，需要修改它的前驱节点、以及后继节点
* @param node
* @return
*/
private E unlink(Node<E> node) {
final E element=node.item;
final Node<E> pred=node.prev;
final Node<E> succ=node.next;
if(pred==null){
first=succ;
}else{
pred.next=succ;
}
if(succ==null){
last=pred;
}else{
succ.prev=pred;
}
// 防止内存泄漏：把node节点占用的资源释放掉
node.prev=null;
node.next=null;
node.item=null;
size--;
return node.item;
}
/**
* 删除指定元素
* 需要遍历链表
* @param o
* @return
*/
public boolean remove(Object o){
if(o==null){
Node<E> f=first;
while(f!=null){
// 遍历链表
if(f.item==null){
unlink(f);
return true;
}
f=f.next;
}
}else{
Node<E> f=first;
while(f!=null){
// 遍历链表
if(o.equals(f.item)){
unlink(f);
return true;
}
f=f.next;
}
}
return false;
}
/**
* 修改
* @param index
* @param element
* @return
*/
public E set(int index,E element){
// index在[0,size-1]范围内则合法，否则抛出IndexOutOfBoundException
checkElementIndex(index);
Node<E> x=node(index);
E oldVal=x.item;
x.item=element;
return oldVal;
}
private void checkElementIndex(int index) {
if(!(index>=0 && index<size) ){
// 如果下标不在范围内：抛出异常
throw new IndexOutOfBoundsException(index+"");
}
}
/**
* 找到索引为index的Node节点
* @param index
* @return
*/
private Node<E> node(int index) {
if(index<(size>>1)){
// 从first节点开始遍历
Node<E> x=first;
for(int i=0;i<index;i++){
x=x.next;
}
return x;
}else{
Node<E> x=last;
for(int i=size-1;i>index;i--){
x=x.prev;
}
return x;
}
}
/**
* 查：得到索引处的值
* @param index
* @return
*/
public E get(int index){
checkElementIndex(index);
return node(index).item;
}
public int size(){
return size;
}
}
测试：
public class Test {
public static void main(String[] args) {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
for (int i = 0; i < list.size; i++) {
System.out.println(list.get(i));
}
list.remove(0);
list.set(1, 5);
for (int i = 0; i < list.size; i++) {
System.out.println(list.get(i));
}
}
}
网友评论