数据结构之List(一) 手写单链表
1.线性表
线性表有两种结构:顺序存储结构和链式存储结构.
顺序存储结构的常见应用:ArrayList
链式存储结构的常见应用:LinkedList
下面我们首先分析链式结构中的单链表:
常见的链表格式有单链表、单循环链表、双链表、以及双循环链表,下面主要分析单链表,实现增删改查以及逆序
LinkedList源码分析
我们先来分析一下LinkedList源码,然后我们再参照其手写单链表
首先,LinkedList是一个双链表,从它的源码我们就可以看出:
private static class Node<E> {
E item;
Node<E> next;//指向下一条item
Node<E> prev;//指向上一条item
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList有一个私有的静态内部类Node,Node中有两个成员变量:next和prev,这两个成员变量分别指向下一条item和上一条item,在C语言里面主要是用指针来表示,java取消了指针,都是用引用来指向对象.
其次,分析一下LinkedList的几个重要方法:
添加元素,add
删除元素,remove
查找元素,get
我们暂时简单的分析一下LinkedList的源码,我们放到后面与ArrayList一起详细分析
先看add方法,LinkedList的add方法有两个重载:
一个是只含有一个Object参数的add方法,此方法是将object添加至末尾.
另一个是包括location和object参数的add方法,location表示object要插入的位置
再看remove方法,和add方法是一一对应的,所以我们在这就暂时不看了
最后看看get方法:Linkedlist对查找进行了一个简单的优化,因为是双向链表,所以既可以从头往后开始查也可以从尾部向前开始查,所以他先判断location是处于前半部分还是后半部分,如果处于后半部在从最后开始查,时间复杂度减少了一半.
public E get(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}
2.手写单链表
简单分析了一下LinkedList的部分源码,我们现在开始准备手写单链表,当然只是简单的实现.包括增删查方法.
首先,咱们分析好需要哪些因素:
1.内部类Node
2.成员变量size,用来记录链表的长度
3.成员变量head和last,分别表示链表的首部和尾部
4.我们要实现的增删查以及转置方法
一、首先参照LinkedList定义一个静态内部类,当然,我们只需要next,不需要prev,具体代码如下:
private static class Node<T>{
T item;//表示当前节点的对象
Node<T> next;//指向下一节点的对象
public Node(T item) {
this.item = item;
}
}
二、定义一个int型成员变量size,用于记录单链表的长度.
三、定义Node型成员变量head和last.
四、下面我们开始真正的撸码:
1.add(T newItem)方法:
public void add(T newItem) {
Node newNode=new Node(newItem);
if(last==null) {//第一次向内添加对象
head=newNode;
last=newNode;
}else {//非第一次
last.next=newNode;//将老的list的最后一个对象的next指向新加入元素
last=newNode;//将新元素赋给last
}
size++;//size加1
}
2.add(int location,T newItem)方法,这个方法可以分为三部分
添加至头部
添加至尾部
往中间插入
好了,不多说,上代码
public void add(int location,T newItem) {
if(location >= 0 && location <= size) {
if(size!=0) {
//判断是不是往头或者尾部添加
Node<T> node=new Node<T>(newItem);
if(location==0) {
//往头部添加
node.next=head;
head=node;
size++;
}else if(location==size) {
//往尾部添加
add(newItem);
}else {
//往中间添加
Node<T> prevNode=head;
Node<T> nextNode=head.next;
int i=1;
while(i<location) {
prevNode=nextNode;
nextNode=nextNode.next;
i++;
}
prevNode.next=node;
node.next=nextNode;
size++;
}
}else {
add(newItem);//当size==0时,说明是第一次添加
}
}else {
throw new IndexOutOfBoundsException();//直接抛异常
}
}
我们先写好get方法,get方法比较简单:
public T get(int location) {
if(location>=size||location<0) {
throw new IndexOutOfBoundsException();//直接抛异常
}else {
Node<T> node=head;
int i=0;
while(i<location) {
node=node.next;
i++;
}
return node.item;
}
}
下面开始分析remove方法:remove方法也有两个重载(移除指定位置的元素和移除指定的元素),当然,移除指定的元素是指第一个,我们也可以写移除所有符合条件的方法,无疑就是从头遍历到尾,所以这里就不做介绍了.当然,我们还可以像LinkedList那样添加,removeFirst和removeLast方法.
public T remove(int location) {
if(location>=size||location<0) {
throw new IndexOutOfBoundsException();//直接抛异常
}else {
if(location==0) {
//移除头部
head=head.next;
return head.item;
}else{
if(size-1==0) {
head=head.next;
return head.item;
}else {
int i=1;
Node<T> prev=head;
Node<T> cur=prev.next;
Node<T> next=cur.next;
while(i<location) {
prev=cur;
cur=next;
next=next.next;
// System.out.println(prev.item+"==="+cur.item+"==="+next.item);
i++;
}
prev.next=next;
return cur.item;
}
}
}
}
public boolean remove(Object o) {
if(size<=0) {
throw new IndexOutOfBoundsException();//直接抛异常
}
Node<T> node=head;
int i=0;
while(node!=null) {
if (node.item.equals(o)) {
remove(i);
return true;
}
i++;
node=node.next;
}
return false;
}
好了,至此大部分主要方法已经实现,只剩下转置了.
转置主要有两种方式:1.循环转置
循环转置的主要思想就是:从第二个元素开始,一次将每一次将当前的next指向上一个元素.详见下图:
好了,上代码:
public void reverse() {
if(head==null||head.next==null) {
return;
}
Node<T> prev=head;
Node<T> curr=head.next;
Node<T> tmp;
while(curr!=null) {
tmp=curr.next;
curr.next=prev;
prev=curr;
curr=tmp;
}
last=prev;
head.next=null;
head=last;
}
下面再简单介绍一下另一种转置方式:递归方式转置,话不多说,先上代码
public void reverse(Node<T> head) {
if(head==null||head.next==null) {
this.head=head;//将未入栈的初始list的尾部赋给head
return;
}
reverse(head.next);//压栈
head.next.next=head;//出栈
head.next=null;
last=head;//最后一个出栈的赋给last
}
画个图解释一下,会比较好理解
好了,今天单链表手写就到这里了.后面抽时间总结一下ArrayList和LinkedList的源码
