数据结构---链表（二）【不带头双向非循环】
文章目录
- 双向链表的模拟实现
- 带头单向非循环链表的模拟实现
- ArrayList 和 LinkedList 的区别
双向链表中有 val 域，next 域 ，prev 域。next 指向下一个节点，prev指向前一个节点
双向链表的模拟实现
import linkedlistdemo.MySingleList;
import java.util.List;
public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
//打印链表
public void show() {
ListNode cur = head;
while(cur != null) {
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含key
public boolean contains(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//计算链表长度size
public int size() {
ListNode cur = head;
int count = 0;
while(cur != null) {
count++;
cur = cur.next;
}
return count;
}
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(head == null) {
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(head == null) {
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
//任意位置插入，第一个结点为0号下标
public void addIndex(int index,int data) {
if(index < 0 || index > size()) {
return;
}
if(index == 0) {
addFirst(data);
}
if (index == size()) {
addLast(data);
}
ListNode node = new ListNode(data);
ListNode cur = searchNode(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
private ListNode searchNode(int index) {
ListNode cur = head;
int count = 0;
while(count != index) {
cur = cur.next;
count++;
}
return cur;
}
//删除val值为key的结点
public void remove(int key) {
if(head == null) return;
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == head) {
if(cur.next == null) {
cur = null;
}else {
head = head.next;
head.prev = null;
}
return;
}
if(cur == last) {
cur.prev.next = null;
last = cur.prev;
return;
}
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
return;
}
cur = cur.next;
}
}
//删除所有值为key的结点
public void removeAll(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == head) {
if(cur.next == null) {
cur = null;
return;
}else {
cur.next.prev = null;
head = head.next;
}
}else if(cur == last) {
cur.prev.next = null;
last = cur.prev;
}else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
cur = cur.next;
}
}
//清除链表
public void clear() {
ListNode cur = head;
ListNode curN = null;
while(cur != null) {
curN = cur.next;
cur.next = null;
cur.prev = null;
cur = curN;
}
head = null;
last = null;
}
}
带头单向非循环链表的模拟实现
public class MySingleList {
//创建节点类
static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
public Node () {
}
}
//创建链表类,包含关于操作链表的方法
public static class LinkedList {
private Node head;//头结点
public LinkedList() {
head = null;//带头空链表
}
//头插
public void addFirst(int val) {
Node newNode = new Node(val);
newNode.next = head;
head = newNode;
}
//尾插
public void addLast(int val) {
Node newNode = new Node(val);
if(head == null) {
head = newNode;
return;
}
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
//获取链表的长度
public int size() {
int count = 0;
Node cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//打印链表
public void print() {
Node cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}
//在第pos个位置插入节点
public void addIndex(int pos, int val) {
if (pos <= 0 || pos > size()+1) {
throw new PosOutOfException("下标位置不合法");
}
if (pos == 1) {
addFirst(val);
}else if(pos == size()+1){
addLast(val);
}else {
//在第pos个位置插入，cur需要走pos-2次，此时cur指向目标位置的前驱
Node cur = head;
for (int i = 0; i < pos - 2; i++) {
cur = cur.next;
}
Node newNode = new Node(val);
newNode.next = cur.next;
cur.next = newNode;
}
}
//删除第pos个位置的结点
public void remove(int pos) {
if (pos <= 0 || pos > size() + 1) {
throw new PosOutOfException("下标位置不合法");
}
if(pos == 1) {
head = head.next;
return;
}
//cur走pos-2后，cur指向目标位置的前驱
Node cur = head;
for (int i = 0; i < pos-2; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
}
//删除值为key的节点
public void removeVal(int key) {
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
return;
}
Node ret = findLastNode(key);
if(ret == null) {
return;
}
ret.next = ret.next.next;
}
//找到值为key的前一个节点
public Node findLastNode(int key) {
if(head == null) return null;
Node cur = head.next;
Node pre = head;
while(cur != null) {
if(cur.val == key) {
return pre;
}
pre = cur;
cur = cur.next;
}
return null;
}
//查找是否包含节点值为key的节点
public boolean contains(int key) {
if(head == null) {
return false;
}
Node cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
}
}
ArrayList 和 LinkedList 的区别
