链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。由于不必须按顺序存储，链表的插入和删除操作可以达到O(1)的复杂度
链表和数组
链表和数组的区别
- 数组静态分配内存，链表动态分配内存。
- 数组在内存中是连续的，链表是不连续的。
- 数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素
- 查找的时间复杂度是O(N)。
- 数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删
- 除不需要移动其他元素，时间复杂度是O(1)。
数组的优点
- 随机访问性比较强，可以通过下标进行快速定位。
- 查找速度快
数组的缺点
- 插入和删除的效率低，需要移动其他元素。
- 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。
- 内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
- 数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。
链表的优点
- 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
- 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
链表的缺点
查找的效率低
单链表
单链表.png
头指针指向头结点；
普通Node即用于数据存储和直接后继指针存储的节点；
尾结点即链表中最后一个节点，其指针域next为空，其后无节点；
//
// LinkList.m
// LinkDemo
//
// Created by 李台辉 on 2021/4/12.
//
#import "LinkList.h"
/// 节点
@interface Node : NSObject
// 保存value
@property (nonatomic, strong) NSObject *ele;
// 指向下一个节点
@property (nonatomic, strong) Node *next;
@end
@implementation Node
- (instancetype)initWithEle:(NSObject *)ele next:(Node *)next{
if (self = [super init]) {
_ele = ele;
_next = next;
}
return self;
}
@end
@interface LinkList ()
/// 存链表的头节点
@property (nonatomic, strong) Node *first;
/// 节点个数
@property (nonatomic, assign) NSInteger size;
@end
@implementation LinkList
/// 返回链表节点个数
- (NSInteger)size{
return _size;
}
- (BOOL)isEmpty{
return self.size == 0;
}
//获取obj在链表中的索引
- (NSInteger)indexOfObject:(NSObject *)obj{
Node *node = self.first;
// 从头节点开始，依次比对 ele
for (int i = 0; i < self.size; i ++) {
if ([obj isEqual:node.ele]) return i;
node = node.next;
}
return -1;
}
// 是否包含某个对象
- (BOOL)isContainObject:(NSObject *)obj{
NSInteger index = [self indexOfObject:obj];
return index != -1;
}
#pragma - mark 增删改查
// 增
//插入obj到指定位置
- (void)addObject:(NSObject *)obj atIndex:(NSInteger)index{
if (index <0) {
NSLog(@"索引不对");
return;
}
if (index > self.size) {
NSLog(@"索引太大");
return;
}
// 添加到头节点
if (index == 0) {
// 创建节点，将节点的next 指向当前头节点
Node *node = [[Node alloc] initWithEle:obj next:self.first];
// 更新头节点
self.first = node;
}else{
// 获取index 前面一个的节点
Node *preNode = self.first;
for (int i = 0; i < index - 1 ; i ++) {
preNode = preNode.next;
}
//构建node
Node *insertNode = [[Node alloc] initWithEle:obj next:preNode.next];
//前一个节点指向插入的节点
preNode.next = insertNode;
}
self.size ++ ;
}
// 头部
- (void)addObjectToHead:(NSObject *)obj{
[self addObject:obj atIndex:0];
}
// 尾部
- (void)addObject:(NSObject *)obj{
[self addObject:obj atIndex:self.size];
}
// 删
- (void)removeObjectAtIndex:(NSInteger)index{
if (index <0) {
NSLog(@"索引不对");
return;
}
if (index > self.size -1) {
NSLog(@"越界");
return;
}
if (index == 0) {
self.first = self.first.next;
}else{
//获取index前面的一个节点
Node *preNode = self.first;
for (int i = 0; i < index - 1 ; i ++) {
preNode = preNode.next;
}
// 获取index 的下一个节点
Node *nextNodel = preNode.next.next;
//前一个节点指向后一个节点
preNode.next = nextNodel;
}
self.size --;
}
// 清空
- (void)clear{
self.size = 0;
self.first = nil;
}
/// 改
- (void)setObject:(NSObject *)obj AtIndex:(NSInteger)index{
//获取index 节点
Node *node = self.first;
for (int i = 0; i < index ; i ++) {
node = node.next;
}
node.ele = obj;
}
/// 查
- (NSObject *)objectAtIndex:(NSInteger)index{
if (index <0) {
NSLog(@"索引不对");
return nil;
}
if (index > self.size -1) {
NSLog(@"越界");
return nil;
}
Node *node = self.first;
for (int i = 0; i < index ; i ++) {
node = node.next;
}
return node.ele;
}
- (NSString *)description{
NSMutableString *string = [NSMutableString string];
[string appendString:@"["];
Node *node = self.first;
// 遍历链表
for (int i = 0; i < self.size; i ++ ) {
[string appendString:[NSString stringWithFormat:@"%@",node.ele]];
if (i != self.size -1) {
[string appendString:@","];
}
//更新当前节点
node = node.next;
}
[string appendString:@"]"];
return string;
}
@end
单链表反转
public class ListNode {
public var val: Int
public var next: ListNode?
public init() {
self.val = 0; self.next = nil;
}
public init(_ val: Int) {
self.val = val; self.next = nil;
}
public init(_ val: Int, _ next: ListNode?) {
self.val = val; self.next = next;
}
}
递归方式
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
// 空链 或者一个节点
if (head == nil || head?.next == nil) {
return head
}
// 递归调用
let newHead = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return newHead
}
}
迭代方式
class Solution1 {
func reverseList(_ head: ListNode?) -> ListNode? {
// 空链 或者一个节点
if (head == nil || head?.next == nil) {
return head;
}
//保存当前节点指针
var curr = head
// 新的头节点指针
var newHead : ListNode? = nil
// 从当前链表的第一个节点开始循环，直到最后一个节点
while curr != nil {
// 临时指针，执行当前节点的下一个节点，以便后面能访问到下一个节点
let nextTemp = curr?.next
// 后面节点的next指向前面一个节点
curr?.next = newHead
// 更新 newhead
newHead = curr
// 当前节点后移
curr = nextTemp
}
return newHead
}
}
网友评论