1.链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 可以形象的理解，在逻辑上来看，链表就像是一节节火车车厢。
链表的分类：链表的结构有很多种，单向或双向、带头或不带头、循环或不循环。这篇文章就从最简单的链表结构讲起———不带头单向非循环链表(单链表)。
2.单链表模拟实现
为了更好的学习对于单链表的操作。我们自己模拟实现一些基本的功能。
1.准备工作
接口
package List;
public interface IList {
//头插法
void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
//清空
public void clear() ;
//打印
public void display() ;
}通过实现接口中的抽象方法实现单链表增删查改的实现。
单链表的定义
单链表(SinglyLinkedList)的定义需要定义单个节点ListNode。单个节点有data存储数据，next存储下一个节点的引用。同时单链表还需要一个成员变量head存储单链表的头位置。基于以上的需要可以把ListNode定义为单链表的内部类。
public class SinglyLinkedList {
public class ListNode{
public int data;
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public ListNode head;
}2.具体接口实现
添加
头插
@Override
public void addFirst(int data) {
ListNode newnode = new ListNode(data);
newnode.next = head;
head = newnode;
}尾插
@Override
public void addLast(int data) {
ListNode newnode = new ListNode(data);
//链表为空
if(head == null){
head = newnode;
return;
}
//链表不为空，找尾尾插
ListNode cur = head;
while (cur.next != null){
cur = cur.next;
}
cur.next = newnode;
}在index位置插入
private void CheckIndex(int index){
int len = this.size();
if(index < 0 || index > len){
throw new IllegalIndexException("index不合法");
}
}
@Override
public void addIndex(int index, int data) {
try {
CheckIndex(index);
ListNode newnode = new ListNode(data);
if(index == 0){
addFirst(data);
}
if(index == size()){
addLast(data);
}
ListNode cur = head;
while(index - 1 != 0){
cur = cur.next;
index--;
}
newnode.next = cur.next;
cur.next = newnode;
}catch (IllegalIndexException e){
e.printStackTrace();
}
}删除
删除找到第一个key值
@Override
public void remove(int key) {
if(head == null){
return;
}
//解决头节点问题
if(head.data == key){
head = head.next;
return;
}
ListNode cur = head;
while(cur.next.data != key){
cur = cur.next;
}
ListNode del = cur.next;
cur.next = del.next;
}删除所有等于key的值
@Override
public void removeAllKey(int key) {
if(head == null){
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null){
if(cur.data == key){
prev.next = cur.next;
}else {
prev = cur;
}
cur = cur.next;
}
//解决头节点data等于key的情况
if(head.data == key){
head = head.next;
}
}查找
@Override
public boolean contains(int key) {
ListNode cur = head;
while (cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}得到size
@Override
public int size() {
int count = 0;
ListNode cur = head;
while(cur != null){
count++;
cur = cur.next;
}
return count ;
}清空
@Override
public void clear() {
ListNode cur = head;
while(cur != null){
ListNode ret = cur;
cur.next = null;
cur = ret.next;
}
head = null;
}打印
@Override
public void display() {
ListNode cur = this.head;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}2.链表oj
看这篇文章：单链表oj练习(C语言版)
虽然是C语言完成的，但是做题的思想是一样的。
3.LinkedList的模拟实现
LinkedList是java标准库提供的双向链表的实现。还是一样为了更好的理解并运用，先自己模拟实现一个。
1.准备工作
接口
接口和上面的单链表接口一样。
MyLinkedList的定义
和上面的单链表不同的是ListNode里多一个prev用于存储上一个节点的引用和MyLinkedList多一个成员last存储双向链表的尾。
2.具体接口实现
添加
@Override
public void addFirst(int data) {
ListNode newnode = new ListNode(data);
if(head == null){
head = last = newnode;
}else {
newnode.next = head;
head.prev = newnode;
head = newnode;
}
}
@Override
public void addLast(int data) {
ListNode newnode = new ListNode(data);
if(head == null){
head = last = newnode;
}else {
last.next = newnode;
newnode.prev = last;
last = newnode;
}
}
private void CheckIndex(int index){
if(index < 0 || index > size()){
throw new IllegalIndexException("index位置不合法");
}
}
private ListNode FindIndexnode(int index){
ListNode cur = head;
while(index-1 > 0){
cur = cur.next;
index--;
}
return cur;
}
@Override
public void addIndex(int index, int data) {
try {
CheckIndex(index);
if(index == 0){
addFirst(data);
}
if(index == size()){
addLast(data);
}
ListNode newnode = new ListNode(data);
ListNode cur = FindIndexnode(index);
newnode.next = cur;
cur.prev.next = newnode;
newnode.prev = cur.prev;
newnode.next = cur;
}catch(IllegalIndexException e){
e.printStackTrace();
}
}
删除
@Override
public void remove(int key) {
ListNode cur = head;
while(cur != null){
if(cur.data == key){
if(cur == head){
head = head.next;
if(head != null){
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if (cur.next == null) {
last = last.prev;
} else {
cur.next.prev = cur.prev;
}
}
return;
}
cur = cur.next;
}
}
@Override
public void removeAllKey(int key) {
ListNode cur = head;
while(cur != null){
if(cur.data == key){
if(cur == head){
head = head.next;
if(head != null){
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if (cur.next == null) {
last = last.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}查找 打印 得到size
和单链表一样，本质都是遍历链表
清空
@Override
public void clear() {
ListNode cur = head;
while(cur != null){
ListNode Curn = cur.next;
cur.prev = null;
cur.next = null;
cur = Curn;
}
head = last = head;
}4.LinkedList的使用
1.构造
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}2.其他方法
